Codeforces Round #222 (Div. 1) B. Preparing for the Contest
解法
二分探索します。
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; }