榆次网站建设,网站通栏设计素材,免费云服务器网站有哪些,两学一做专栏网站目录
题目
分析
参考代码 题目 题目描述 一个果园里#xff0c;多多已经将所有的果子打了下来#xff0c;而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并#xff0c;多多可以把两堆果子合并到一起#xff0c;消耗的体力等于两堆果子的…目录
题目
分析
参考代码 题目 题目描述 一个果园里多多已经将所有的果子打了下来而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。 每一次合并多多可以把两堆果子合并到一起消耗的体力等于两堆果子的重量之和。可以看出所有的果子经过n-1次合并之后就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花大力气把这些果子搬回家所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1并且已知果子的种类数和每种果子的数目你的任务是设计出合并的次序方案使多多耗费的体力最少并输出这个最小的体力耗费值。 例如有3种果子数目依次为129。可以先将1、2堆合并新堆数目为3耗费体力为3。接着将新堆与原先的第三堆合并又得到新的堆数目为12耗费体力为12。所以多多总共耗费体力31215。可以证明15为最小的体力耗费值。 输入格式 输入包括两行。 第一行是一个整数n(1n10000)表示果子的种类数。 第二行包含n个整数用空格分隔第i个整数ai(1ai20000)是第i种果子的数目。 输出格式 输出包括一行这一行只包含一个整数也就是最小的体力耗费值。输入数据保证这个值小于2的31次方。 样例 样例输入
3
1 2 9 样例输出
15 数据范围与提示 对于30的数据保证有n1000 对于50的数据保证有n5000 对于全部的数据保证有n10000。 分析
这道题我主要是采用优先队列的方式来做,主要是因为优先队列便于排序.
接下来咱们边上代码边讲
priority_queueint,vectorint,greaterint q;
定义优先队列,这里我定义的是小根堆(从小到大),因为优先队列默认的是大根堆(从大到小),为了避免与输入流符号误认,要特地把他们分开.
for(int i1;in;i){cintmp;q.push(tmp);
}
输入,入列,优先队列的好处就是边入列边排序,比sort快.
while(q.size()1){kq.top();q.pop();k1q.top();q.pop();k1k,sumk1;q.push(k1);k10;
}
合并果子的过程,大家应该都能看懂吧 .
最后把sum输出就行了.接下来就是参考代码
参考代码
#includebits/stdc.h
using namespace std;
const int MAX10005;
typedef unsigned long long ull;
int tmp,n,sum,k,k1;
priority_queueint,vectorint,greaterint q;
int main(){ios::sync_with_stdio(false);cinn;for(int i1;in;i){cintmp;q.push(tmp);}while(q.size()1){kq.top();q.pop();k1q.top();q.pop();k1k,sumk1;q.push(k1);k10;}coutsumendl;return 0;
}如果你不想让你的代码超时,手动开O2哦
#pragma GCC optimize(2)
