问题标题: 酷町堂:4057搬花 咋错了(优先队列)

0
0
已解决
高杨
高杨
资深守护
资深守护

自己编的样例也过了,不知道咋错了

#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


0
已采纳
王子健
王子健
初级天翼
初级天翼

你想复杂了,直接输入n个k,压入优先队列(从小往大的)里,然后while循环条件是q.size()>1(等于1不可以,因为要取上面两个栈顶),然后两个数取栈顶,两个数的和压入栈,最后拿一个ans += 那两个数的和

具体代码如下:
输入+压栈:

while:

定义:

输出ans即可

 

PS:加我QQ告诉我4071

0
赵逸凡
赵逸凡
初级启示者
初级启示者

22行改为while(!q.empty())

还有,你的思路很错乱啊,t1放在循环外面?

@王子健 你不用问作业了

 

 

赵逸凡在2020-08-09 11:18:03追加了内容

@高杨 就算照你这么写,在第二次取出队首的时候也要弹出这个元素啊,你应该在循环里面取两次队首 并pop(如果队列为空则break),然后t+=这两次队首,最后输出

我要回答