题解 P6033 【合并果子 加强版】

· · 题解

题解里的都是模拟两个队列贪心，这里给出一种船新的做法

相信合并果子的原题大家都做过，就是每次找两个最小值堆一起

这题显然也是要这么做的，但不同的是数据规模大大加强，10^7带一只log是过不去的

仔细观察数据发现，题目中的a_i比较小，只有10^5，因此我们可以尝试从这里入手

发现最大的a_i也比n小很多，根据抽屉原理可知，一定有重复的a_i，而且是很多。我们把a_i相同的当成一类，这样就最多只有10^5类

把每类按大小排好，从前往后考虑，同一类的元素肯定是两两互相配对，如果是奇数那么就把多出来的这个和下一类挑出来一个匹配即可

code

#include<bits/stdc++.h>
#define maxn 100005
#define ll long long
using namespace std;
int n,x,Num[maxn],Lst;
ll Ans;
struct lc{
    ll x;int data;
    bool operator <(const lc b)const{return x<b.x;}
};
multiset<lc> Q;
multiset<lc>::iterator Now,Cnt,cnt;
inline int read(){
    int ret=0;char ch=getchar();
    while (ch<'0'||ch>'9') ch=getchar();
    while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
    return ret;
}
int main(){
    n=read();
    for (int i=1;i<=n;i++) Num[read()]++;
    for (int i=1;i<=1e5;i++) if (Num[i]) Q.insert((lc){i,Num[i]});
    while (Q.size()>1){
        Now=Q.begin();ll A=(*Now).x;int B=(*Now).data-Lst;
        Lst=0;
        if (!B){Q.erase(Now);continue;}
        if (B>1){
            Ans+=(ll)((int)B/2)*2*A;
            if (B&1){
                Cnt=Now;Cnt++;
                Ans+=(ll)A+(*Cnt).x;
                Q.insert((lc){A+(*Cnt).x,1});
                Lst=1;
            }
            Q.insert((lc){2*A,B/2});
        }
        else{
            Cnt=Now;Cnt++;
            Ans+=(ll)A+(*Cnt).x;
            Q.insert((lc){A+(*Cnt).x,1});
            Lst=1;
        }
        Q.erase(Now);
    }
    printf("%lld",Ans);
    return 0;
}