题目分析
开始还真没看出来这题跟 \(\text{P1090}\) 合并果子 的关系。
其实只要逆向思考,把拆分看成效果一样的合并就可以了。而与合并果子不同的是,在这题当中我们可以分成 \(3\) 组,显然这样比分成 \(2\) 组更优。
按照以下思路,不难写出以下代码(其实就是将合并果子的板子改一下):
while(q.size()>=3){
int top1=q.top();q.pop();int top2=q.top();q.pop();int top3=q.top();q.pop();
ans+=top1+top2+top3;
q.push(top1+top2+top3);
}
这样我们就顺利过掉了第一个样例。
接着观察第二个样例,发现当 \(n\) 为偶数时,如果 \(3\) 组分下去,最后一定会剩下 \(2\) 组需要单独合并。那我们不如在开始的时候就将最小的 \(2\) 组进行合并,这样就解决了。
贴上代码
#include<bits/stdc++.h>
#define int long long
#define debug puts("Shiina_Mashiro_kawaii")
#define ok puts("Yes")
#define no puts("No")
using namespace std;
int read(){
int x=0,f=1;char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-48;
c=getchar();
}
return x*f;
}
const int maxn=1e5+5;
int n;
int ans;
int a[maxn];
priority_queue<int,vector<int>,greater<int> > q;
inline void init(){
n=read();
for(register int i=1;i<=n;++i) q.push(read());
}
signed main(){
init();
if(n%2==0){
int top1=q.top();q.pop();int top2=q.top();q.pop();
ans+=top1+top2;
q.push(top1+top2);
}
while(q.size()>=3){
int top1=q.top();q.pop();int top2=q.top();q.pop();int top3=q.top();q.pop();
ans+=top1+top2+top3;
q.push(top1+top2+top3);
}
printf("%lld",ans);
}
标签:CF884D,int,题解,top,top3,top2,pop,top1
From: https://www.cnblogs.com/yizhixiaoyun/p/17094020.html