资深守护
自己编的样例也过了,不知道咋错了
#include <bits/stdc++.h>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <sstream>
#include <queue>
using namespace std;
priority_queue<int,vector<int>,greater<int> > q;
int n,t,t1,sum;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>t;
q.push(t);
}
t1=q.top();
for(int i=n-1;i>0;i--)
{
t=0;
t+=t1;
q.pop();
t+=q.top();
t1=t;
sum+=t;
}
cout<<sum;
return 0;
}
4057 搬花经验值:800
题目描述 Description
在一个花园里,琪亚娜已经将所有的花摘了下来,而且按花的不同种类分成了不同的堆。琪亚娜决定把所有的花合成一堆。每一次合并,琪亚娜可以把两堆花合并到一起,消耗的体力等于两堆花的重量之和。可以看出,所有的花经过n-1次合并之后,就只剩下一堆了。琪亚娜在合并花堆时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些花搬回家,所以琪亚娜在合并花时要尽可能地节省体力。假定每朵花重量都为1,并且已知花的种类数和每种花的数目,你的任务是设计出合并的次序方案,使琪亚娜耗费的体力最少,并输出这个最小的体力耗费值。
例如有3种花,数目依次为1,2,9。可以先将 1、2堆合并,新堆数目为3,耗费体力为3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为 12。所以琪亚娜总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
输入描述 Input Description
包括两行
第一行是一个整数n(1 <= n <= 10000),表示花的种类数
第二行包含n个整数,用空格分隔,第i个整数ai(1 <= ai <= 20000)是第i种花的数目
输出描述 Output Description
包括一行,这一行只包含一个整数,也就是最小的体力耗费值
样例输入 Sample Input
3 1 2 9
样例输出 Sample Output
15
数据范围及提示 Data Size & Hint
对于30%的数据,保证有n <= 1000
对于50%的数据,保证有n <= 5000
对于全部的数据,保证有n <= 10000
初级天翼
你想复杂了,直接输入n个k,压入优先队列(从小往大的)里,然后while循环条件是q.size()>1(等于1不可以,因为要取上面两个栈顶),然后两个数取栈顶,两个数的和压入栈,最后拿一个ans += 那两个数的和
具体代码如下:
输入+压栈:
while:
定义:
输出ans即可
PS:加我QQ告诉我4071