Codeforces Round #222 (Div. 1) B. Preparing for the Contest

問題

codeforces.com

解法

二分探索します。

check(x) = (担当する人が最大で x 日働いて良い場合の, 各問題の人の割り振りを表す配列。割り振れない時は ひとつ目の要素を -1 にする) とすると, 以下のようにすれば最小コストで担当者を割り振れます(前準備で問題は難易度が高い順にソートしておく)。

• i 問目の問題以上の難易度を解ける人を priority_queue に突っ込む(給料の低い人が優先されるようにする)。
• 一番給料の低い人に [i, i+x) の x 問を担当してもらう。その後, i += x

const int MAX = 100010;
int n, m, s;

int a[MAX], b[MAX], c[MAX];
pii P[MAX], ap[MAX];

vector<int> check(int x) {
    vector<int> ret(m);
    priority_queue<pii, vector<pii>, greater<pii> > que;
    int pp = 0;
    ll sum = 0;
    for (int i = 0; i < m; i+=x) {
        while (pp < n && P[pp].first >= ap[i].first) {
            int index = P[pp].second;
            que.push(pii(c[index], index));
            pp++;
        }
        if (que.empty()) {
            ret[0] = -1;
            return ret;
        }
        auto p = que.top(); que.pop();
        sum += p.first;
        if (sum > s) {
            ret[0] = -1;
            return ret;
        }
        for (int j = i; j < min(i+x, m); j++) {
            ret[ap[j].second] = p.second;
        }
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < n; i++) cin >> c[i];
    for (int i = 0; i < m; i++) ap[i] = pii(a[i], i);
    for (int i = 0; i < n; i++) P[i] = pii(b[i], i);
    int low = 0, high = m;
    sort(ap, ap+m);
    reverse(ap, ap+m);
    sort(P, P+n);
    reverse(P, P+n);
    while (high - low > 1) {
        const int med = (low+high)/2;
        auto v = check(med);
        if (v[0] != -1) high = med;
        else low = med;
    }
    auto v = check(high);
    if (v[0] == -1) cout << "NO" << endl;
    else {
        cout << "YES" << endl;
        for (int i = 0; i < m; i++) cout << v[i]+1 << " ";
        cout << endl;
    }
    return 0;
}