CDOJ 1263 The Desire of Asuna 贪心
2024-09-02 12:51:43
The Desire of Asuna
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
ZYHAzwraith用自己心爱的键盘换来了很多支漂亮的荧光棒!
一天,他准备用一条由很多个莹光圈相互连接而成的荧光链送给女神Asuna。每个荧光圈只能由一支荧光棒首尾相接成一个环得到。现在他手中有 n 条荧光链,为了最后把这些链拼接成一条链,每次他可以选择任意一条荧光链中的任意一个荧光圈并用魔法把这个圈断开,然后用这个断开的荧光圈去连接任意两条荧光链使之成为一条。
现在ZYHAzwraith想知道最少需要多少次才能把这些荧光链链拼接成一条长链?
Input
第一行是一个整数 n ( 1≤n≤2000),
表示有 n 条荧光链。
接下来一行有 n 个数,每个数 ai (1≤ai≤105)表示第 i 条链由 ai 个荧光圈相互连接
Output
输出一个整数表示最少的次数。
Sample input and output
Sample Input | Sample Output |
---|---|
3 |
1 |
3 |
2 |
Hint
第一组样例解释:
Source
第七届ACM趣味程序设计竞赛第三场(正式赛)
贪心。
我们选择长度减小的链,一定是可选的,并且长度最小的链。
我们选择合并的链,一定是当前长度最大的两条链。
为什么?
假设所有的链的长度都是无限长,这道题的答案毫无疑问就是 n-1 。
但是长度并不是无限长的,所以我们可以通过 使得链长度-1 的这个操作,去除一些链,使得答案比 n-1 小
很容易可以看出,我们之前的贪心策略,可以使得尽量多的链在 长度-1 这个阶段就被消去了。
所以这道题就结束了。
我们选择长度减小的链,一定是可选的,并且长度最小的链。
我们选择合并的链,一定是当前长度最大的两条链。
为什么?
假设所有的链的长度都是无限长,这道题的答案毫无疑问就是 n-1 。
但是长度并不是无限长的,所以我们可以通过 使得链长度-1 的这个操作,去除一些链,使得答案比 n-1 小
很容易可以看出,我们之前的贪心策略,可以使得尽量多的链在 长度-1 这个阶段就被消去了。
所以这道题就结束了。
<span style="font-family:KaiTi_GB2312;font-size:18px;">#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int a[2005];
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
int l=1,r=n,ans=0;
while(l<r)
{
a[l]--;
r--;
ans++;
a[r]+=a[r+1]+1;
if(a[l]==0)
l++;
}
cout<<ans<<endl;
}
return 0;
}</span><span style="font-family:Open Sans, Helvetica Neue, Helvetica, Helvetica, Arial, sans-serif;font-size:32px;">
</span>
最新文章
- BZOJ 2049 [Sdoi2008]Cave 洞穴勘测 ——Link-Cut Tree
- freemarker springmvc配置异常
- JavaWeb学习计划
- Js弹出层,弹出框代码
- jquery的几个国内CDN加速节点
- BZOJ 1115: [POI2009]石子游戏Kam [阶梯NIM]
- 容器启动脚本报错:exec user process caused ";no such file or directory";
- ftruncate(改变文件大小)
- 向集合中添加自定义类型--建议在自定义类型的时候要重写equals方法
- wrapper class (Integer 为例)
- UltraEdit配置
- js,需要更多源字符
- 铁乐学python_day29_模块与包学习4
- NIO中的Buffer
- 直播【95秀】JNI 基本实现 简洁
- Spring学习笔记--自动装配Bean属性
- oracle高水位问题
- 大数据领域两大最主流集群管理工具Ambari和Cloudera Manger
- 使用 Python 编写脚本并发布
- 推荐开源靶场Vulhub
热门文章
- python安装OpenCV后import cv2报错解决办法
- 【html】 iframe 和 frameset 的区别
- shiro学习(五、springboot+shiro+mybatis+thymeleaf)
- centos7安装配置zabbix监控
- SQL基础:语句执行顺序
- Vue-----this.$nextTick()
- 描述Cookie和Session的作用,区别和各自的应用范围,Session工作原理
- zookeeper配置文件说明
- Delphi GetCommModemStatus函数
- 修改tomcat 端口