murnana's diary

のんびり書きます。マサカリまってます(震えながら

ABC080 D - Recording

D - Recording

解説動画: youtu.be

テレビ番組を録画したい

  • N個のテレビ番組を録画したい
  • チャンネルはC個
  • i個のテレビ番組は、時刻s~時刻tまで、チャンネルCiで放送される
  • 録画機は、時刻S~時刻Tまで録画したいとすると、S-0.5~Tまでの時間、他のチャンネルの録画をすることができない(同じチャンネルならできる)
  • N個すべてを録画するとき、必要な録画機の最小数は?

解き方

累積和を使う

  1. 配列aを用意する
  2. 変数bを一つ用意する
  3. すべての番組の最を1とする
  4. その番組の終わりに-1とする
  5. a配列を順に追う 1があったらbに+1,-1なら-1を足していく
  6. bの最大値を求める

ほへーって感じです。ほへー。
累積和はアルゴリズムの一つのようです。

paiza.hatenablog.com