题目: [NOIP2004]合并果子 ,哈哈,我们今天来看一道比较简单的题嘛,这是选自NOIP上的一道题,好了,我们一起来看看题意吧:
考虑到直接复制题目,或者截屏的方式不是很方便阅读,我就把直接题目链接放下面!
题目传送门: [NOIP2004]合并果子
思路
:
我们用两个队列,一个队列装已经排好序的元素,一个队列装合并后的元素,然后我们取出队头小的一个并出队,然后我们
再
取出队头小的一个并出队,然后把取出的两个元素相加,加入到合并元素的队列中去!具体的我们直接看代码!
我们来看看成功AC的代码吧:
#include<bits/stdc++.h> using namespace std; int n; int a[10010]; queue<int> q1,q2;//用两个队列,方便理解 int main(){ cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); for(int i=1;i<=n;i++) q1.push(a[i]); int ans=0; for(int i=1;i<n;i++){ int x[3]; for(int j=1;j<=2;j++){//找到队头小的 if(q2.empty()||!q1.empty()&&q1.front()<q2.front()){ x[j]=q1.front(); q1.pop(); }else{ x[j]=q2.front(); q2.pop(); } } ans+=x[1]+x[2]; q2.push(x[1]+x[2]); } cout<<ans; return 0; }