这个不能贪心做。滚雪球会越滚越大的。应该是小雪球们合成才是最优。
by Terrible @ 2020-05-12 11:45:54
打开题解学学堆,每次找最小的果子合成,然后再放进堆里。
by Terrible @ 2020-05-12 11:46:53
这不是队列和单调队列吗 ……
by 一只书虫仔 @ 2020-05-12 12:05:53
最好还是用priroity_queue做
by zheysq_147 @ 2020-05-12 12:06:05
用STL优先队列几行就过了,而手写堆。。。
by zyk7 @ 2020-05-12 12:19:46
建议用priroity_queue哦
by Sora1336 @ 2020-05-12 12:21:23
@[18111207031dsz](/user/339978) 贪心是没问题的,你的思路有问题
我现在忙不开,稍后回复您
by 人间温柔 @ 2020-05-12 13:09:50
@[18111207031dsz](/user/339978) 这道题的贪心策略就是每次取出数量之和最小的两堆果子合并,因为题目说合并时顺序任意,所以才可以这样做。但是《石子合并》就不对了,他只能用DP来做,因为《石子合并》的要求是每次合并只能合并相邻的两堆。
下面是我的代码,用到的是优先队列$priority\_queue$:希望对你有用呀:
```cpp
#include<bits/stdc++.h>
#include<queue>
using namespace std;
int main ()
{
long long n;
priority_queue<long long,vector<long long>,greater<long long> >p;//优先队列,小根堆
long long a;
long long s=0;
long long ans=0;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a;
p.push(a);
}
for(int i=1;i<n;i++)
{
ans=p.top();//每次的top函数返回的是队列里面的最小值
p.pop();
ans+=p.top();
p.pop();
s+=ans;
p.push(ans);//合并后就是一个更大的堆,要推入
}
cout<<s;
return 0;
}
```
by 人间温柔 @ 2020-05-12 13:29:47
@[18111207031dsz](/user/339978) 如果您还是不明白,可以继续at我,我看到了会回复的。
by 人间温柔 @ 2020-05-12 13:32:03
@[18111207031dsz](/user/339978) 就算按照你的方法,你的代码还是有问题。
你想一下啊,假设两队果子重量5,8,合并后重量13,。到后面你这堆13的还要和其他的果子合并,所以你的$num[]$要把这个13搞进去。这样用数组这个数据结构会很麻烦
by 人间温柔 @ 2020-05-12 13:38:58