HDU1800 Flying to the Mars 【贪心】
Flying to the Mars
In the year 8888, the Earth is ruled by the PPF Empire . As the population growing , PPF needs to find more land for the newborns . Finally , PPF decides to attack Kscinow who ruling the Mars . Here the problem comes! How can the soldiers reach the Mars ?
PPF
convokes his soldiers and asks for their suggestions . “Rush … ” one soldier answers. “Shut up ! Do I have to remind you that there isn’t any road to the Mars from here!” PPF replies. “Fly !” another answers. PPF smiles :“Clever guy ! Although we haven’t got
wings , I can buy some magic broomsticks from HARRY POTTER to help you .” Now , it’s time to learn to fly on a broomstick ! we assume that one soldier has one level number indicating his degree. The soldier who has a higher level could teach the lower , that
is to say the former’s level > the latter’s . But the lower can’t teach the higher. One soldier can have only one teacher at most , certainly , having no teacher is also legal. Similarly one soldier can have only one student at most while having no student
is also possible. Teacher can teach his student on the same broomstick .Certainly , all the soldier must have practiced on the broomstick before they fly to the Mars! Magic broomstick is expensive !So , can you help PPF to calculate the minimum number of the
broomstick needed .
For example :
There are 5 soldiers (A B C D E)with level numbers : 2 4 5 6 4;
One method :
C could teach B; B could teach A; So , A B C are eligible to study on the same broomstick.
D could teach E;So D E are eligible to study on the same broomstick;
Using this method , we need 2 broomsticks.
Another method:
D could teach A; So A D are eligible to study on the same broomstick.
C could teach B; So B C are eligible to study on the same broomstick.
E with no teacher or student are eligible to study on one broomstick.
Using the method ,we need 3 broomsticks.
……
After checking up all possible method, we found that 2 is the minimum number of broomsticks needed.
In a test case,the first line contains a single positive number N indicating the number of soldiers.(0<=N<=3000)
Next N lines :There is only one nonnegative integer on each line , indicating the level number for each soldier.( less than 30 digits);
4
10
20
30
04
5
2
3
4
3
4
1
2
water
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxn 3002
using std::sort; int arr[maxn];
bool vis[maxn]; bool cmp(int a, int b){
return a > b;
} int main()
{
int n, i, j, tmp, ans;
while(scanf("%d", &n) == 1){
for(i = 0; i < n; ++i)
scanf("%d", arr + i);
sort(arr, arr + n, cmp);
memset(vis, 0, sizeof(vis));
for(i = 0, ans = n; i < n; ++i){
if(vis[i]) continue;
tmp = arr[i];
for(j = i + 1; j < n; ++j){
if(vis[j]) continue;
if(tmp > arr[j]){
tmp = arr[j]; --ans;
vis[j] = 1;
}
}
}
printf("%d\n", ans);
}
return 0;
}
最新文章
- Graphviz绘制百家争鸣图
- linux bash 笔记
- Java面试题系列 提高Java I/O 性能
- Effective C++ -----条款50:了解new 和delete 的合理替换时机
- Redis 集群方案- 主从切换测试
- Redis多机功能介绍
- .NET MVC 依赖注入 来龙去脉
- mysql 表格中的数据量过大,修改数据库字段信息会花费很长的时间
- windows 7 memcached报failed to install service or service already installed的解决方案
- ASP.NET 运行
- Leetcode 39 40 216 Combination Sum I II III
- iOS 调试 之 打印
- SAP成都研究院35岁以上的开发人员都去哪儿了?
- OCR技术初识
- 如何引用GitHub的静态资源文件 js css
- Linux下python2.7安装pip
- 洛谷 P1478 陶陶摘苹果(升级版)
- select 详解
- Ant压缩与解压缩
- wiggle-subsequence
热门文章
- RN原生的安卓UI组件
- 刚毕业去面试Python工程师,这几道题太难了,Python面试题No11
- Dajngo admin
- 快捷键,命令之tab/ history / alias / ls / cd / mkdir / touch /tree /cp /mv /rm /cat /head/grep
- 我的Python分析成长之路8
- (原)UICollectionView的基本使用
- solr 日志配置
- WPF IP地址输入控件的实现
- 模板<;最小生成树>;
- WordPress实现前台登录功能