「CF230A」龙的战争（详细分析）

战争（详细分析）"/>

「CF230A」龙的战争（详细分析）

题目描述

Kirito现在被困在一个MMORPG游戏当中，为了离开这个游戏，他现在必须和n条龙进行战斗，Kirito和这n头龙都有一个力量值，用整数表示，Kirito最初的力量值为s。如果在Kirito和第i头龙(1 ≤ i ≤ n)的对决当中，Kirito的力量不大于龙的力量xi，那么，Kirito将输掉对决并死亡。如果Kirito的力量大于龙的力量，那么，Kirito将打败这条龙并且升级获得额外的力量提升。
现在，Kirito可以按照任意顺序和这些龙进行决斗，请问，Kirito能否离开这个游戏，即Kirito能够战胜所有的n头龙并且没有死亡。

输入格式：
题目包含多组输入
第一行输入两个数字s和n(1 ≤s ≤ 1e4, 1 ≤ n≤ 1e3)，表示Kirito的初始力量值和龙的数量。
接下来n行，每行输入两个数字xi和yi(1 ≤xi ≤ 1e4, 0 ≤ yi≤ 1e4),表示第i头龙的力量以及Kirito击败这头龙能够获得的额外力量值。

输出格式：
如果Kirito能够离开这个游戏，则输出”YES”,否则，则输出”NO”.

样例

样例输入：
2 2
1 99
100 0
样例输出：
YES

样例输入：
10 1
100 100
样例输出：
NO

算法分析

这一题是一道非常简单的贪心题，只需要一个简单的排序，就可以完成。
最佳贪心策略就是比较X _i ，最小的最先做，从而积累Y _i 。

思路很简单，代码量也不多。

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int M=10005;
struct node{int xi,yi;
}a[M];
bool cmp(node x,node y){return x.xi<y.xi;
}
int main(){int s,n;while(scanf("%d %d",&s,&n)!=EOF){for(int i=1;i<=n;i++){scanf("%d %d",&a[i].xi,&a[i].yi);}sort(a+1,a+1+n,cmp);bool flag=false;for(int i=1;i<=n;i++){if(s>a[i].xi){s+=a[i].yi;}else{flag=true;break;}}if(flag==true)printf("NO\n");else{printf("YES\n");}}
}