hdu5884（多叉哈夫曼树）

hdu5884

题意

给出 n 个数，每次选择不超过 k 个数合并（删掉这些数，加入这些数的和），花费为合并的这些数的和，要求最后只剩下一个数，问 k 最小取多少。

分析

二分 k，合并数的时候可以按照哈夫曼树构树的原理来进行合并。因为新形成的数存在递增的单调性，所以可以开一个数组（队列）存储新生成的数，将原来的数组排序，通过取两个数组最小的 k 个数，将和放置到队尾，直到只剩下一个数。

如果 \((n-1)\%(k-1)\neq0\)，说明不能正好合并得到一个数，此时要先选择\((n-1)\%(k-1)+1\)个数进行合并。

code

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 200005;

int a[MAXN], b[MAXN];

int n, s;

ll disp(int k) {

    int h1 = 0, h2 = 0, t2 = 0;

    int cnt = n;

    b[t2] = 0;

    ll res = 0;

    for(h1 = 0; h1 < (n - 1) % (k - 1) + 1; h1++) {

        b[t2] += a[h1];

        cnt--;

        res += a[h1];

    }

    if(b[t2] > 0) { t2++; cnt++; }

    while(cnt != 1) {

        int c = 0;

        b[t2] = 0;

        while(c < k) {

            if(h1 < n && (h2 == t2 || a[h1] < b[h2])) {

                b[t2] += a[h1];

                res += a[h1];

                h1++;

                cnt--;

            } else {

                b[t2] += b[h2];

                res += b[h2];

                h2++;

                cnt--;

            }

            c++;

        }

        t2++;

        cnt++;

    }

    return res;

}

int main() {

    ios::sync_with_stdio(0);

    cin.tie(0);

    int T;

    for(cin >> T; T--;) {

        cin >> n >> s;

        ll ans = 0;

        for(int i = 0; i < n; i++) {

            cin >> a[i];

        }

        sort(a, a + n);

        int l = 2, r = n, mid;

        while(l < r) {

            mid = (l + r) / 2;

            if(disp(mid) <= s) r = mid;

            else l = mid + 1;

        }

        cout << l << endl;

    }

    return 0;

}