题解报告:hdu1205吃糖果(插空法)
2024-09-08 08:09:56
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1205
Problem Description
HOHO,终于从Speakless手上赢走了所有的糖果,是Gardon吃糖果时有个特殊的癖好,就是不喜欢将一样的糖果放在一起吃,喜欢先吃一种,下一次吃另一种,这样;可是Gardon不知道是否存在一种吃糖果的顺序使得他能把所有糖果都吃完?请你写个程序帮忙计算一下。
Input
第一行有一个整数T,接下来T组数据,每组数据占2行,第一行是一个整数N(0<N<=1000000),第二行是N个数,表示N种糖果的数目Mi(0<Mi<=1000000)。
Output
对于每组数据,输出一行,包含一个"Yes"或者"No"。
Sample Input
2
3
4 1 1
5
5 4 3 2 1
Sample Output
No
Yes
解题思路:这是一道排列问题,就是将若干种类的糖果按要求排列,相同种类的糖果不能相邻。这时考虑插空法。先考虑数量最多的那一种糖果(假设这种糖果有n个)先间隔排好,留出n-1个空格。剩下的糖果总数大于等于n-1,就可以使得数量最多的那一种糖果不会相邻,再将剩下的糖果按种类依次插入之前已经排好糖果的空隙中,则可以满足题目的要求,输出yes。如果剩下的糖果总数小于n-1,数量最多的那一种糖果一定会出现相邻的状况,因此输出no。因此,设数量最多的那一种糖果的数量为N,所有糖果总数为A,如果N-1<=A-N,即2N-1<=A,输出yes,否则输出no。
AC代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int T,N,m,maxnum;//插空法:用一种数目最多的进行排列,让剩下的数目依次插空
LL sum;//规律:如果剩下的数目大于等于有maxsum-1这么多空,则yes,否则No
cin>>T;
while(T--){
cin>>N;
maxnum=sum=;
while(N--){
cin>>m;
sum+=m;
maxnum=max(maxnum,m);//找出最大的数
}
if(sum-maxnum>=maxnum-)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return ;
}
最新文章
- Excel&mdash;&mdash;使用OFFSET、MATCH、COUNTA实现二级菜单
- (一)Linux相关内容的简介
- Scrum Meeting 6-20151208
- 团队项目2.0软件改进分析MathAPP
- 复制转移sharepoint 2010 designer做的list workflow的方法
- 语义化的html结构的好处
- ubuntu创建文件夹快捷方式命令
- composer 272解决
- 删除项目中的.svn文件
- DB2事务日志已满的解决方法
- JavaScript目录
- 通过设置cookie实现单点登录
- Linux的grep命令详解
- javascript基础(二)类型转换
- JS清除DIV的选中状态
- RabbitMQ 使用(一)
- [51nod1443]路径和树
- hihocoder #1142 : 三分&#183;三分求极值
- vue中怎么全局引入sass文件
- selenium官方网站文档,testng官方网站文档
热门文章
- 利用NSA的MS17-010漏洞利用工具实现Win 7和Win Server 2008系统入侵
- 【algorithm】尾递归
- 用Lazarus编写第一个程序Pascal版的hello world
- Android中个人推崇的数据库使用方式
- 通过通过url routing解决UIViewController跳转依赖
- React通过Ajax获取数据
- 第一个WordCount类运行
- Filter 详解
- 二.OC基础--1,对象的存储细节,2,#pragma mark指令,3,函数和对象方法的区别,4,对象和方法之间的关系 ,5.课堂习题
- 并不对劲的bzoj1853:[SCOI2010]幸运数字