P6033 / SYOJ #261 分果子 / 合并果子[加强版]

· · 题解

【大体思路】

桶排+枚举

【详解】

小范围数据可以使用优先队列，而现在数据范围太大做法不是 O(N) 就会超时。

我们来从本质上考虑一下优先队列都实现了什么。首先肯定是把所有元素都从小到大排好序，然后取出两个，再把和扔回去，并且继续保持序列有序。

前两步我们用一个数组 a 也能实现，发现元素最大 1e5 ，可以用桶排，但是放回元素和并且维护序列有序的操作没法 O(1) 进行。

一个数组不行，两个数组还真行。把算出的和放到一个新数组 b 里，每次取元素的操作变成了三种情况：取两个之前没合并过的、取一个没合并的和一个合并过的、取两个合并过的。

把这三种情况都算一下，选代价最少的那个，把加和无脑丢到 b 数组里就可以，因为这些和一定是越求越大，这就保证了 b 数组的有序。

有一些小细节，这里不再赘述。纯模拟，代码为了直观，一些判断条件选择保留了自己原始的样貌。基本上都是重复的操作，写起来也不太用费脑子，跑的还挺快。

记得开long long！！！

【代码】

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N = 1e7 + 10;
const ll inf = 0x3f3f3f3f3f3f3f3f;
ll n, a[N], tot;
ll sum, x, y, maxa, b[N];
ll read() {
    ll x = 0, y = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') y = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch ^ 48);
        ch = getchar();
    }
    return x * y;
}
int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        x = read();
        b[x]++;
        maxa = max(maxa, x);
    }
    for (int i = 1; i <= maxa && tot <= n; i++) {
        while (b[i] >= 1) {
            a[++tot] = i;
            b[i]--;
        }
    }
    a[tot + 1] = inf;
    memset(b, 0x3f, sizeof(b));
    int x = 1;
    int y = 1;
    tot = 0;
    ll res1, res2, res3;
    for (int i = 1; i < n; i++) {
        res1 = res2 = res3 = inf;
        if (x < n && x + 1 <= n) {
            res1 = a[x] + a[x + 1];
        }
        if (x <= n && y <= tot) {
            res2 = a[x] + b[y];
        }
        if (y <= tot && y + 1 <= tot) {
            res3 = b[y] + b[y + 1];
        }
        if (res1 == min(res1, min(res2, res3))) {
            sum += res1;
            x += 2;
            b[++tot] = res1;
        } else if (res2 == min(res1, min(res2, res3))) {
            sum += res2;
            x++;
            y++;
            b[++tot] = res2;
        } else {
            sum += res3;
            y += 2;
            b[++tot] = res3;
        }
    }
    printf("%lld", sum);
    return 0;
}