解析

不難發(fā)現(xiàn)每次都應(yīng)合并最大的一對(duì)，從而使局部最優(yōu)帶動(dòng)整體最優(yōu)
sort就會(huì)很自然的想到
但是問題是合并完之后的新值可能已經(jīng)不是當(dāng)前最大了（WA。。qwq）
于是想到每次循環(huán)sort一遍，結(jié)果n^2logn又超時(shí)了。。。
在一位高人的指引下，我學(xué)廢了賴皮的priority queue（具體見代碼）

代碼

#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<queue> #include<functional> #include<vector> using namespace std; bool cmp(int x,int y){return x>y; } int main() {int x,n,k;priority_queue<int,vector<int>,less<int> >q;//就是這個(gè)queue，里面的元素會(huì)自動(dòng)排序scanf("%d%d",&n,&k);for(int i=1;i<=n;i++){scanf("%d",&x);q.push(x);} for(int i=1;i<=n-1;i++){int a,b;a=q.top();//返回隊(duì)首元素q.pop();//彈出隊(duì)首元素b=q.top();q.pop();a+=b;a/=k;q.push(a);//加入元素}int ans=q.top();printf("%d",ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的priority_queue+贪心：运输（题解）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。