原题传送门:http://codeforces.com/problemset/problem/230/A
Kirito is stuck on a level of the MMORPG he is playing now. To move on in the game, he's got to defeat all n dragons that live on this level. Kirito and the dragons have strength, which is represented by an integer. In the duel between two opponents the duel's outcome is determined by their strength. Initially, Kirito's strength equals s.
If Kirito starts duelling with the i-th (1 ≤ i ≤ n) dragon and Kirito's strength is not greater than the dragon's strength xi, then Kirito loses the duel and dies. But if Kirito's strength is greater than the dragon's strength, then he defeats the dragon and gets a bonus strength increase by yi.
Kirito can fight the dragons in any order. Determine whether he can move on to the next level of the game, that is, defeat all dragons without a single loss.
The first line contains two space-separated integers s and n (1 ≤ s ≤ 104, 1 ≤ n ≤ 103). Then n lines follow: the i-th line contains space-separated integers xi and yi (1 ≤ xi ≤ 104, 0 ≤ yi ≤ 104) — the i-th dragon's strength and the bonus for defeating it.
On a single line print "YES" (without the quotes), if Kirito can move on to the next level and print "NO" (without the quotes), if he can't.
2 2 1 99 100 0
YES
10 1 100 100
NO
In the first sample Kirito's strength initially equals 2. As the first dragon's strength is less than 2, Kirito can fight it and defeat it. After that he gets the bonus and his strength increases to 2 + 99 = 101. Now he can defeat the second dragon and move on to the next level.
In the second sample Kirito's strength is too small to defeat the only dragon and win.
分析:排序+贪心
把那些能被打掉的小怪兽排前面,如果这样都不能顺利通关的话,那肯定不能。
#include<cstdio> #include<algorithm> using namespace std; #define MAXN 1100 struct Dr{ int str; int bon; }; bool cmp(Dr a,Dr b){ return a.str<b.str; } int s,n,flag; Dr d[MAXN]; int main() { while(scanf("%d%d",&s,&n)==2) { flag = 1; for(int i=0;i<n;i++){ scanf("%d%d",&d[i].str,&d[i].bon); } sort(d,d+n,cmp); for(int i=0;i<n;i++){ if(s>d[i].str) { s+=d[i].bon; } else{ flag = 0; break; } } if(flag){ printf("YES\n"); }else{ printf("NO\n"); } } return 0; }
相关推荐
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 185A - Plant 全测试点49个
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
Codeforces round 678 D2_Codeforces_源码
# sublime-plugin-for-codeforces 自定义构建,用于从 codeforces 获取测试用例并检查程序是否正确。 平台:GNU/Linux 语言:Python2.7.9 描述:这个程序从 codeforces 中获取测试用例,并告诉你程序的输出是否与...
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
PDF-CodeForces问题 PDF文件中的CodeForces问题 利用CodeForces提取在这个库中的文件 ,文件夹名代表来自CodeForces网址contests`的ID,每个文件夹包含比赛的问题。 有关CodeForces竞赛的疯狂事实 CodeForces上有937...
codeforces-plugin-sublime-text 注意:仅适用于 C++ 代码。 它能做什么? 编译你的 C++ 代码,构建它,获取测试用例,在上面运行你的代码,比较输出。 它不做什么: 通过互联网神奇地识别您的问题并进行判断。 ...
codeforces-js Codeforces JS
Codeforces Round #723 (Div. 2).md
打codeforces的神器
来自2012,2013年国际信息奥林匹克金牌得主许昊然
使用 C# + WPF 开发 --- 还在发愁打了那么多场比赛都没有进入首页么? 还在为了前 5 的 hacker 名额阅读千份代码么? 是的,你没有看错! 这是一个 Edu & Div.3 轮 Open hacking 错误代码自动查找器!...