mayoko’s diary

プロコンとかいろいろ。

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;
}