P76025 依次挑战 — 题解

专题： 排序与贪心
适用题目： 新生 OJ 本地题包中的 P76025，不要直接用于外站同名题。

解题思路

按挑战所需能力 x 从小到大排序，逐个检查当前能力是否严格大于其要求，完成后获得收益。

复杂度

时间 $O(n\log n)$，额外空间 $O(n)$。

易错点

判断条件是 s > x，而不是 s >= x。

C11 参考程序

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <limits.h>

typedef struct {long long x,y;} Dragon;
int cmp_dragon(const void *p,const void *q) {
    const Dragon *a=(const Dragon*)p,*b=(const Dragon*)q;
    return (a->x > b->x)-(a->x < b->x);
}
int main(void) {
    long long strength;int n;scanf("%lld%d",&strength,&n);
    Dragon *a=malloc(n*sizeof(Dragon));
    for(int i=0;i<n;i++)scanf("%lld%lld",&a[i].x,&a[i].y);
    qsort(a,n,sizeof(Dragon),cmp_dragon);
    int ok=1;
    for(int i=0;i<n;i++){
        if(strength<=a[i].x){ok=0;break;}
        strength+=a[i].y;
    }
    puts(ok?"YES":"NO");free(a);return 0;
}

C++17 参考程序

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define nl '\n'

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll s;
    int n;
    cin>>s>>n;
    vector<pair<ll,ll>> a(n);
    for(auto &x:a)cin>>x.first>>x.second;
    sort(a.begin(),a.end());
    bool ok=true;
    for(auto [x,y]:a){
        if(s<=x){
            ok=false;
            break;
        }
        s+=y;
    }
    cout<<(ok?"YES":"NO")<<nl;
    return 0;
}

题解建议设置为训练结束后开放。普通判题无法验证是否实际使用指定函数或 STL。