P7390 「EZEC-6」造树

· · 题解

更好的阅读体验

考虑贪心，按权值排序，对于枚举到的节点i，我们要尽量让这个点和小的点连边，考虑到我们要保证这棵树存在，所以留1的度数用来让这棵树能和剩下的点连起来，于是每次枚举的连通块都需要预留至少1度数和后面的点连边。

我们用一个指针j表示[1, j]已经变成了一个连通块，那么对于枚举到的i就从j往后开始连，所以任意时刻我们连出来的一定仅有一个连通块的，根据上面的结论，我们再维护这个连通块的度数使他保持有至少为1的度数即可。

我写题解一般都写的很少的，但这次是验题的工作，所以写一下详细证明。

若当前枚举到的i使得[1, j]连通块最后仅剩i这个点有1的度数，且j + 1的点度数为1，那么连这个点就会导致无法和后面的点连通，所以要找到后面第一个度数大于1的点k相连，然后再处理i到k之间的点直到k的度数为1或区间内的点被连完，如果这个区间还有剩下的点就继续寻找下一个k，直到[1, k]为一个连通块或者已经连到了n，由于题目保证树存在，所以连到n的时候已经不需要保证度数可以直接相连。

若已知a > b > c > d，在所有将他们分成两对分别求乘积的和的方案中，最大值为ab + cd。

所以对于上述过程，因为在任意时刻，全局最小的权值会和当前该权值能连边的最小权值相乘，所以最终结果一定是最大值。

可以反证，首先初始的边集为空集，肯定为最优解的子集，如果最小的权值a没有和它能连的最小权值b相连，而和c相连，那么一定会存在一个比a大的权值d和b相连，这违背了上述结论，所以这个解一定不是最优的，故上述结论构成的子集一定是最优解的子集，于是如果当前为最优解的子集，之后每步加的边都是最优解的子集。

这个过程具有对称性，所以对权值的排序从小到大和从大到小是等价的。

而我们保证了[1, j]为连通块，每次相连一定与[j + 1, n]的点相连，对于k来说，因为i到k路径上的点度数均为1，所以和k相连的点不可能与之前的连通块构成环，剩下的点与[k + 1, n]的点相连，这时可以理解为这些点已经不存在，并且后面的点度数改变，由于题目保证可以构成树，加上我们限制了每个点至少要保留1的度数，所以这个过程毫无影响正确性。

时间复杂度O(n)，这里为了复杂度对应用的桶排，实际上用sort可以在2s内通过所有数据。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define mp(x, y) make_pair(x, y)
#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);

using namespace std;

const int N = 1e7 + 10;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

struct NODE {int d, val;} dat[N], t[N];

int n, m = 5e5, last, cnt[N];

long long ans;

namespace STD {
    unsigned seed;
    unsigned rnd(unsigned x) {
        x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x;
    }
    int rad(int x, int y) {
        seed = rnd(seed); return seed % (y - x + 1) + x;
    }
    void init() {
        seed = read();
        for(int i = 1; i <= n; i++) t[i].d = 1, t[i].val = rad(1, 500000);
        for(int i = 1; i <= n - 2; i++) t[rad(1, n)].d++;
    }
}

void sort() {
    for (int i = 1; i <= n; i++) cnt[t[i].val]++;
    for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for (int i = 1; i <= n; i++) dat[cnt[t[i].val]--] = t[i];
}

int main() {
    int type = read(); n = read();
    if (type == 1) STD::init(); else {
        for (int i = 1; i <= n; i++) t[i].d = read();
        for (int i = 1; i <= n; i++) t[i].val = read();
    }
    sort(); last = 1;
    for (int i = 1, j = 2, k = 2; i <= n; i++, j = max(j, i + 1)) {
        while (dat[i].d == 0 && i <= n) i++; if (i > n) break;
        while (dat[i].d > 1) {
            while (dat[j].d == 0) j++; if (dat[j].d > 1) last = j;
            ans += 1ll * dat[i].val * dat[j].val; dat[i].d--; dat[j].d--; j++;
        }
        if (last == i) {
            k = max(j, k); while (dat[k].d <= 1 && k < n) k++;
            ans += 1ll * dat[i].val * dat[k].val; dat[i].d--; dat[k].d--; i = j;
            while (i < k && dat[k].d > 1) {
                ans += 1ll * dat[i].val * dat[k].val; dat[i].d--; dat[k].d--; i++;
            }
            if (dat[k].d == 1) last = i; else last = k; i--;
        } else {
            while (dat[j].d == 0 && j < n) j++; if (dat[j].d > 1) last = j;
            ans += 1ll * dat[i].val * dat[j].val; dat[i].d--; dat[j].d--; j++;
        }
    }
    printf("%lld", ans);
    return 0;
}