题解：P6033 [NOIP 2004 提高组] 合并果子 加强版

· · 题解

思路

请先了解本题弱化版中的贪心思路，接下来讲如何通过本题。
发现后合并的两堆果子一定比先合并的两堆果子都要重，所以合并完了，后合并出来的那堆也一定比先合并的那堆要重。
于是发现每次往堆里面插入的值具有单调性，先插入的小。发现这个性质后，就不需要用堆来维护了，可以直接往一个队列里面插入，队列中前面的元素先插入，也就小一些。

发现值域较小，所以使用计数排序，就不需要排序的 \log 了。

时间复杂度为 O(A+n)。

代码

#include<bits/stdc++.h>
#define ull unsigned long long
namespace fastIO {
#define BUF_SIZE 100010
    bool IOerror = 0;
    inline char nc() {
        static char buf[BUF_SIZE], *p1 = buf + BUF_SIZE, *pend = buf + BUF_SIZE;
        if(p1 == pend) {
            p1 = buf;
            pend = buf + fread(buf, 1, BUF_SIZE, stdin);
            if(pend == p1) {
                IOerror = 1;
                return -1;
            }
        }
        return *p1++;
    }
    inline bool blank(char ch) {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    }
    inline void read(int &x) {
        char ch;
        while(blank(ch = nc()));
        if(IOerror)
            return;
        for(x = ch - '0'; (ch = nc()) >= '0' && ch <= '9'; x = x*10 + ch - '0');
    }
#undef BUF_SIZE
};
using namespace fastIO;
using namespace std;
queue<ull>q2;
queue<int>q1;
ull ans;
int a,n,t[100005];

ull get(){
    bool f1=q1.empty(),f2=q2.empty();
    ull x;
    if(f2||(!f1&&(q1.front()<=q2.front()))){
        x=q1.front();
        q1.pop();
    }
    else{
        x=q2.front();
        q2.pop();
    }
    return x;
}

int main(){
    read(n);
    for(int i=1;i<=n;i++){
        read(a);
        t[a]++;
    }
    for(int i=1;i<=100000;i++){
        if(t[i]>0){
            while(t[i]--)q1.push(i);
        }
    }
    for(int i=1;i<n;i++){
        ull x=get()+get();
        ans+=x;
        q2.push(x);
    }
    printf("%llu",ans);
    return 0;
}