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

A. Dragons

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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

1
2
3
2 2
1 99
100 0

output

复制代码YES

1
YES

input

复制代码10 1 100 100

1
2
10 1
100 100

output

复制代码NO

1
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.

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
</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>

最后

以上就是无私乌龟最近收集整理的关于Dragons(CodeForces 230A)(贪心和排序）的全部内容，更多相关Dragons(CodeForces内容请搜索靠谱客的其他文章。