Dragons(CodeForces 230A)(贪心和排序）

98 阅读 0 评论 65 点赞

我是靠谱客的博主无私乌龟，最近开发中收集的这篇文章主要介绍Dragons(CodeForces 230A)(贪心和排序），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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 x_i, 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 y_i.

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.

Input

The first line contains two space-separated integers s and n (1 ≤ s ≤ 10⁴, 1 ≤ n ≤ 10³). Then n lines follow: the i-th line contains space-separated integers x_i and y_i (1 ≤ x_i ≤ 10⁴, 0 ≤ y_i ≤ 10⁴) — the i-th dragon's strength and the bonus for defeating it.

Output

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.

Sample test(s)

input
2 2
1 99
100 0

output
YES

input
10 1
100 100

output
NO

Note

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.

题目来源：

http://codeforces.com/problemset/problem/230/A

这题是我们csu暑假集训基础组训练赛(1)的第二题，就是贪心算法，按龙的能量大小，由小到大排序，先干掉能量小的，补充能量，然后干掉大的。

题目不算难，我是用了冒泡排序的，边排序边比较能量大小。不过训练赛的时候没有做出来，因为看题没看清楚，看少了一句非常重要的话——Kirito can fight the dragons in any order.

代码：

</pre><pre name="code" class="cpp"><span style="font-size:18px;">#include<stdio.h>
struct dragon
{
int x;
int y;
};
int main()
{
int n,i,j,s;
bool bo=true;
dragon dra[1001],tem;
scanf("%d%d",&s,&n);
for (i=1;i<=n;i++) scanf("%d%d",&dra[i].x,&dra[i].y);
dra[0].y=0;
for (i=2;i<=n;i++)
{
for (j=n;j>=i;j--)
if (dra[j].x<dra[j-1].x)
{
tem=dra[j];
dra[j]=dra[j-1];
dra[j-1]=tem;
}
if (s<=dra[i-1].x)
{
bo=false;
break;
}
else s=s+dra[i-1].y;
}
if (bo&&s>dra[n].x) printf("YESn");
else printf("NOn");
return 0;
}</span><span style="font-size:14px;">
</span>