首页 技术 正文
技术 2022年11月23日
0 收藏 920 点赞 4,143 浏览 723 个字

题目

原题链接:http://codeforces.com/problemset/problem/884/D

现有一堆小石子,要求按要求的数目分成N堆,分别为a1、a2、…an。具体的,每次选一个堆(其重量为代价),分成2或3堆。求最小的可能代价。

思路

我们反向考虑,就是一个不断合并的过程。当n为奇数,我们总能找到三个最小的合并,直到只剩一堆;当n为偶数,先选择最小的两个合并,再按奇数一样处理。(为了统一起来,添加一个辅助堆,石子个数为0)

代码实现

 #include<stdio.h>
#include<iostream>
#include<queue>
using namespace std; typedef long long ll;
int n; int main()
{
while (scanf("%d",&n) == )
{
priority_queue<ll,vector<ll>,greater<ll> >q;
ll ans = ;
for (int i = ; i < n; i++)
{
int tmp;
scanf("%d", &tmp);
q.push(tmp);
}
if ((n & ) == ) q.push(); //n为偶数,补充一个0
while (q.size() > )
{
ll a = q.top(); q.pop();
ll b = q.top(); q.pop();
ll c = q.top(); q.pop();
ans += (a + b + c);
q.push(a + b + c);
}
q.pop();
printf("%I64d\n", ans);
}
}

参考链接:

http://codeforces.com/blog/entry/55470

http://www.cplusplus.com/reference/queue/priority_queue/

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,257
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,695
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,535
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,306
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,944
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,104