|
|
题目大意：
用一堆桃子和另一堆桃子合并，用合并的桃子再用另一堆桃子合并，直到只剩一堆桃子
明显的，体力等于两堆桃子之和，所以我们经过简单的推理得到
优先合并桃子少的，体力之和最少。
有了策略，我们就可以开始写代码了。
打住！！
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]复制代码
求评价！！！
|
|
|
|
|
发表于 2023-4-9 09:13:32
收藏
置顶卡