はまやんはまやんはまやん

hamayanhamayan's blog

TV Shows [Codeforces Round #523 (Div. 2) D]

http://codeforces.com/contest/1061/problem/D

N個のテレビ番組がある。
i番目はL[i]~R[i]分放送している。
最初はテレビを持っていないが、テレビ1つを初期投資X円、1分につきY円の料金で借りられる。
全てのTV番組を見るためにテレビを適切に借りた時の値段総和の最小値をmod10^9+7で答えよ。

考察過程

1. mod10^9+7で答えよの時点でdpとかで最小を取ってくる感じじゃない
2. 最適方針があるのだろう
3. (区間スケジューリング問題っぽいので、Rでソートして貪欲になにかすればいい?)
4. 眠くて寝た
5. 翌日Benqさんの解法見たら、Lで昇順ソートして貪欲だった

解法

http://codeforces.com/contest/1061/submission/46096636

Lで昇順ソートして考えていこう。
貪欲をする。

i番目のテレビ番組について考える。
テレビの調達には2つ選択肢がある。
1. i番目より前のテレビ番組で使っていたテレビを継続して使う
2. テレビを新しく借りる
どちらも、y*(r-l)は掛かる。他には
1. y*(l-前のTV番組のr)
2. x
だけかかり、これを最小化したい。
ここで貪欲をするのだが、なるべく、lに近いrを採用するようにする。
こうして、TV番組をどんどんくっつけていくような感じで最適に動いていこう。
 
実装ではpriority_queueを用いた。
canuse := CanUseであるが、L[i]よりも小さい視聴済みTV番組のrが降順で入っている
wait := 視聴済みだがL[i]以上のrが昇順で入っている(昇順なので-をつけて入れたり出したりしている)

int N; ll X, Y;
vector<pair<int, int>> V;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> X >> Y;
    rep(i, 0, N) {
        int l, r; cin >> l >> r;
        V.push_back(make_pair(l, r));
    }
    sort(all(V));

    priority_queue<int> canuse, wait;

    mint ans = 0;
    rep(i, 0, N) {
        int l, r;
        tie(l, r) = V[i];

        while (0 < wait.size() and -wait.top() < l) {
            canuse.push(-wait.top());
            wait.pop();
        }

        if (0 < canuse.size()) {
            ans += min(X, Y * (l - canuse.top()));
            canuse.pop();
        }
        else ans += X;

        ans += Y * (r - l);
        wait.push(-r);
    }

    cout << ans << endl;
}