CF884D 题解

ikunTLE · 2024-07-08 18:07:54 · 题解

题目传送门

思路

这道题很像合并果子，不同点是这道题可以选择合并 2 个数，也可以合并 3 个数。没有做过合并果子的建议先去做一做。

与合并果子一样，我们可以用优先队列（priority_queue）将所有数存起来，将小的数放到队列的首端。可以发现，我们每一次操作尽量合并 3 个数，使最终的代价最小。

然而少不了一些毒瘤数据，例如：1 4 4 4 4 4。若按照上文所述，第一次合并 1,4,4 和 4,4,4，第二次合并 9,12，最终代价是 42。然而，正解是先合并 1,4 和 4,4,4，然后合并 4,5,12，代价为 38。

我们发现，当 n 为整数时，最后一次操作只能合并 2 个数。也就是说，在前面的操作中，多了一次合并，使得最终代价更大。为了解决这个问题，我们可以在初始化优先队列时，可以加入一个 0，这样不影响合并的计算或最终代价。

注意事项

• 不开 long long 见祖宗，特别还要注意优先队列中也要开 long long。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
priority_queue<long long,vector<long long>,greater<long long>>pq;
long long sum;//记录最终代价
int main(){
    int n=read();
    for(int i=1;i<=n;++i)
        pq.push(read());
    if(n%2==0)
        pq.push(0);
    while(pq.size()>1){
        //每一次选3个数为最优
        long long x=pq.top();
        pq.pop();
        long long y=pq.top();
        pq.pop();
        long long z=pq.top();
        pq.pop();
        long long temp=x+y+z;
        sum+=temp;//更新代价
        pq.push(temp);
    }
    printf("%lld",sum);
    return 0;
}