Codeforces Round #311 (Div. 2) C. Arthur and Table
Codeforces Round #311 (Div. 2)は不参加です。この問題,一発できちんとした解法書くのが結構難しい気がする(書いてる途中で「あ…」ってなって何回か書き直した)。
解法
ある長さxを最大長にしたいときはxより長い足の長さはすべて消費していなければならない。
この前提のもとで,長さの最大長をxにしてテーブルを安定にするための最小コストを求める。
長さがx未満でコストがaかかるものの数を各コストについて0から順番に調べていく方針で長さxを最大長とするコストを求めると,コストはたかだか200種類しかないことから計算量的に間に合う。
だいぶ雑に書いたので400msかかりました。
const int MAXN = 100100; const int INF = 1<<30; int l[MAXN], d[MAXN]; int n; int need = 0; int already = 0; int L[MAXN], dl[201][MAXN], dd[201]; // 長さnの足の数,コストがnで長さがmの足の数,コストがnの足の数 int calc(int x) { if (L[x] == 0) return INF; int must = n-(L[x]*2-1)-already; int ret = need; for (int i = 0; i <= 200; i++) { int tmp = min(must, dd[i]-dl[i][x]); ret += tmp * i; must -= tmp; if (must == 0) break; } return ret; } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> l[i]; for (int i = 0; i < n; i++) cin >> d[i]; for (int i = 0; i < n; i++) { L[l[i]]++; dl[d[i]][l[i]]++; dd[d[i]]++; } int ans = INF; for (int i = MAXN-1; i > 0; i--) { ans = min(ans, calc(i)); for (int j = 0; j <= 200; j++) { need += j*dl[j][i]; dd[j] -= dl[j][i]; } already += L[i]; } cout << ans << endl; }