1375

tiger

题目大意： 用一堆桃子和另一堆桃子合并，用合并的桃子再用另一堆桃子合并，直到只剩一堆桃子 明显的，体力等于两堆桃子之和，所以我们经过简单的推理得到 优先合并桃子少的，体力之和最少。 有了策略，我们就可以开始写代码了。 打住！！ n是30000，你用冒泡的n方的时间复杂度会超限。 sort的话，经过简单的计算，很明显超限。 分析一下我们的过程： 1.取出两个最少的桃子堆 2.合并成一个放回去 3.重新排序，返回第一步，直到只剩一堆 那么，能够轻松取出和推入元素的，并且能轻松排序的是 优先队列！！！ 上代码！ #include<iostream> #include<cstdio> #include<string.h> #include<algorithm> #include<cmath> #include<queue> using namespace std; priority_queue<long long,vector<long long>,greater<long long> > q; //一定都要写long long int arr[30000]; int n; int main() {         int i,j,m;         int a,b;         long long sum=0;         cin>>n;         for (i=1;i<=n;i++)         {                 scanf("%d",&m);                 //要写scanf，节省时间                 arr=m;                 q.push(m);         }         while(q.size()>1)         {                 a=q.top();                 q.pop();                 b=q.top();                 q.pop();                 q.push(a+b);                 //取出两堆，合并后放回                 sum+=a+b;         }         cout<<sum<<endl;         return 0; } [color=rgb(51, 102, 153) !important]复制代码 求评价！！！

收藏