刷题记录:牛客NC16663[NOIP2004]合并果子
记录 合并 刷题 牛客
2023-09-14 09:12:54 时间
传送门:牛客
题目描述:
在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有
的果子合成一堆。
每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果
子经过n-1次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为
1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,
并输出这个最小的体力耗费值。
例如有3种果子,数目依次为1,2,9。可以先将1、2堆合并,新堆数目为3,耗费体力为3。接着,将新堆与
原先的第三堆合并,又得到新的堆,数目为12,耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明
15为最小的体力耗费值。
输入:
3
1 2 9
输出:
15
当年NOIP提高组的一道题,是一道经典的贪心题,难度并不大,洛谷上还有加强版
对于这道题我们需要用到的是C++里面的优先队列
当然也可以自己手打优先队列(虽然但是,没必要)
对于一般的优先队列,priority_queue<int>pq
,是一个"越小的整数优先级越低的优先队列"
对于另一种"越大的整数优先级越低的优先队列",我们需要加入cmp比较函数(类似于sort)
struct cmp{
bool operator() (const int a,const int b) const{
return a>b;
}
};
priority_queue<int,vector<int>,cmp>pq
并且c++还为我们准备了更加方便的STL写法
priority_queue<int,vector<int>,greater<int> >pq
注意此处最后的两个大于号之间要留有空格,不然编译器会将其当做 >> 运算符
有了优先队列的前置知识之后我们也就不难写出这道题了
对于每一次的合并,我们发现每一堆对之后的影响都是持久的,也就是越早合并的果堆被用到的次数越多,那么显然的,如果我们需要最优解显然是将每一次合并完的最小两个堆进行再一次的合并即可,对于维护这种操作我们使用优先队列(sort会超时)
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define maxn 1000000
#define ll_maxn 0x3f3f3f3f3f3f3f3f
const double eps=1e-8;
//priority_queue<int,vector<int>,greater<int> >pq; 简便写法
struct cmp{
bool operator() (const int a,const int b) const {
return a>b;
}
};
//详细写法
priority_queue<int,vector<int>,cmp>pq;
int main() {
int n;n=read();
int a;
for(int i=1;i<=n;i++) {
a=read();
pq.push(a);
}
int ans=0;
int fi,se;
while(pq.size()>1) {
fi=pq.top();
pq.pop();
se=pq.top();
pq.pop();
ans+=(fi+se);
pq.push(fi+se);
}
cout<<ans<<endl;
return 0;
}
相关文章
- 911完整记录_入院记录书写
- 2.创建一个商店的数据,记录客户及购物情况,有以下三个表组成
- 【错误记录】Unity 安卓打包报错( Platform Android with graphics API OpenGLES3 is not supported with HDRP )
- Linux查看DNS记录的简便方法(linux查dns)
- 表记录合并MySQL中合并相同ID记录(mysql相同id)
- springboot springmvc拦截器 拦截POST、PUT、DELETE请求参数和响应数据,并记录操作日志详解编程语言
- 记录MySQL查询:快速取得一条记录(mysql查询1条)
- MySQL合并数据记录:实现快速合并(mysql合并多条记录)
- 记录MySQL中筛选出唯一记录的技巧(mysql筛选不重复)
- Oracle数据库优化:跟踪记录与分析性能(oracle数据库跟踪)
- 眨一下眼睛竟计算了 25.5 亿次!阿里云实时计算平台 Flink 再创新记录
- Oracle中几条记录相加的技巧(oracle几条记录相加)
- MySQL一行合并多个记录(mysql 一行合并)
- Oracle多行记录合并/连接/聚合字符串的几种方法
- MYSQL中获取得最后一条记录的语句
- SQL合并多行记录的相同字段值
- mysql查询第几行到第几行记录的语句
- mysql中多表删除其中ID相同记录的方法