1 条题解

  • 0
    @ 2026-9-30 12:33:32

    C++ :

    
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    struct P { int a, b; };
    static P p[1005];
    /* 按 (b 降序, a 降序):b 大的先吃能把「进食权」撑大,是使前缀和最大的排法。
       吃第 j 个之前需要有进食权(rights = 1 + Σ_{i<j}(b_i-1) >= 1)。
       a >= 0 ⇒ 取得越多越好,所以取满足全部前缀和 >= 0 的最长前缀。 */
    bool cmp(const P &x, const P &y){
        if(x.b != y.b) return x.b > y.b;
        return x.a > y.a;
    }
    int main(){
        int n;
        if(scanf("%d", &n) != 1) return 0;
        for(int i = 0; i < n; i++) scanf("%d %d", &p[i].a, &p[i].b);
        sort(p, p + n, cmp);
        long long rights = 1, ans = 0;
        for(int i = 0; i < n; i++){
            if(rights < 1) break;
            ans += p[i].a;
            rights += p[i].b - 1;
        }
        printf("%lld\n", ans);
        return 0;
    }
    
    
    • 1

    信息

    ID
    2580
    时间
    1000ms
    内存
    256MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者