東京大学プログラミングコンテスト2011: E. ファーストアクセプタンス

,

正直なところDPすら思い付かなかった。なぜなのか

solution

次のようなスケジューリング問題として言い換えられる: 仕事$i$は実行に$A_i$時間かかって期限は$B_i$、処理する仕事の個数を最大化せよ。 期限の早い順に見る。 $i$個目まで見て$j$個処理するのにかかる最小の時間を$\mathrm{dp}(i, j)$とする$O(N^2)$が可能。 これを優先度付きqueueで加速すれば$O(N \log N)$。

implementation

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < int(n); ++ (i))
#define ALL(x) begin(x), end(x)
using namespace std;

int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> a(n), b(n);
    REP (i, n) scanf("%d%d", &a[i], &b[i]);
    // solve
    vector<int> order(n);
    iota(ALL(order), 0);
    sort(ALL(order), [&](int i, int j) { return b[i] < b[j]; });
    priority_queue<int> que;
    int sum_que = 0;
    for (int i : order) {
        sum_que += a[i];
        que.push(a[i]);
        if (sum_que > b[i]) {
            sum_que -= que.top();
            que.pop();
        }
    }
    // output
    printf("%d\n", int(que.size()));
    return 0;
}