CodeForces 230A Dragons

你的名字 2022-02-22 16:10 141阅读 0赞

题目衔接：[http://codeforces.com/problemset/problem/230/A][http_codeforces.com_problemset_problem_230_A]

> 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* ≤ 104, 1 ≤ *n* ≤ 103). Then *n* lines follow: the *i*\-th line contains space-separated integers *x**i* and *y**i* (1 ≤ *x**i* ≤ 104, 0 ≤ *y**i* ≤ 104) — 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.

Example

> input
> 
> Copy
> 
>     2 2
>     1 99
>     100 0
> 
> output
> 
> Copy
> 
>     YES
> 
> input
> 
> Copy
> 
>     10 1
>     100 100
> 
> output
> 
> Copy
> 
>     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.

题目大意：给你一个初始值，和n个怪物，杀死这个怪物可以获得能量，问你能不能杀死所有怪物，杀怪的顺序无要求

思路：虽然只是道A题，但这题我感觉可以拿出去吓人，，如果读不懂题意，或者误解了题意，这道题就可能认为是一道DP题……至少我刚开始就想成了dp，其实就是排个序，先杀死所有能杀死的龙，获取他们的能量，如果中间出现不能杀死的，肯定输出NO即可，遍历完输出YES就行了

代码：

/*
    题目大意：
    思路：
    */
    #include<map>
    #include<set>
    #include <vector>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll unsigned long long
    #define inf 0x3f3f3f
    #define esp 1e-8
    #define bug {printf("mmp\n");}
    #define mm(a,b) memset(a,b,sizeof(a))
    #define T() int test,q=1;scanf("%d",&test); while(test--)
    const int maxn=2e5+10;
    const double pi=acos(-1.0);
    const int N=201;
    const int mod=1e9+7;
    struct node
    {
        int s,g;
    } a[maxn];
    bool cmp(node a,node b)
    {
        if(a.s==b.s)
            return a.g>b.g;
        return a.s<b.s;
    }
    int main()
    {
        int ans,n;
        cin>>ans>>n;
        for(int i=0; i<n; i++)
            cin>>a[i].s>>a[i].g;
        sort(a,a+n,cmp);
        for(int i=0; i<n; i++)
        {
            if(ans<=a[i].s)
            {
                printf("NO\n");
                return  0;
            }
            else
                ans+=a[i].g;
        }
        cout<<"YES"<<endl;
        return 0;
    }

[http_codeforces.com_problemset_problem_230_A]: http://codeforces.com/problemset/problem/230/A