DDPC B - DDPC特別ビュッフェⅡ

問題

discovery2016-final.contest.atcoder.jp

解法

ある時間 t までに得られる最大の美味しさを priority_queue で管理します。

時間 t には, t 個のビュッフェを取ることが出来ますが, どのように取るのが良いかというと, 美味しさが大きいものから取るのが良いです(まぁアタリマエ)

具体的にどう実装するかを考えます。

時間 t においては合計で t 個のビュッフェが取れます。時間 t = T[i] なる i の集合について, A[i] を大きい順に並べておくと, とりあえず que.size() が t になるまで A[i] を詰め込めます。

t = T[i] となるビュッフェが que.size() が t になってもまだ残っている場合, que に残っている美味しさの低いものより美味しさの高いビュッフェがあれば, 入れ替えをします。

これを繰り返していくと, que には, 常に「時間 t までに取ることの出来るビュッフェで, 美味しさの合計が最大になる集合」が得られます。

もし que に含まれる数の合計が X を超えているなら, なるべく量が少なくなるように, 小さいものから順に取り除いていきます。

計算量は O(N log N) です。

const int MAXN = 100010;
int T[MAXN], A[MAXN];
vector<int> app[MAXN];
int N, X;

void solve() {
    ll sum = 0;
    priority_queue<int> que;
    int rest = 0;
    for (int i = 1; i < MAXN; i++) {
        rest++;
        int j = 0;
        while (j < (int)app[i].size() && rest > (int)que.size()) {
            que.push(-app[i][j]);
            sum += app[i][j];
            j++;
        }
        while (j < (int)app[i].size()) {
            int tmp = -que.top();
            if (tmp < app[i][j]) {
                que.pop();
                que.push(-app[i][j]);
                sum += app[i][j]-tmp;
            } else break;
            j++;
        }
    }
    if (sum >= X) {
        while (1) {
            int tmp = -que.top();
            if (sum-tmp >= X) {
                sum -= tmp;
                que.pop();
            }
            else break;
        }
    }
    if (sum >= X) cout << que.size() << endl;
    else cout << -1 << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N >> X;
    for (int i = 0; i < N; i++) cin >> T[i];
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) app[T[i]].push_back(A[i]);
    for (int i = 0; i < MAXN; i++) sort(app[i].rbegin(), app[i].rend());
    solve();
    return 0;
}