题解：AT_jag2017summer_day1_k パンプキン

zhangmuning1016 · 2024-11-07 20:02:37 · 题解

题意

给定整数 N ，有 N 张牌，每张牌拿走会扣掉一定的积分，拿走这张牌就可以得到一些积分。得分 \ge0 的情况下，最多能拿走几张牌。

题目思路

这是贪心，要让得到的牌数更多，就要让扣分越少越好。
1.因为是贪心，把 a 数组从小到大排序。
2.遍历 a 数组，每召唤一次，ans 就减去 a_i ，如果 ans \ge 0，说明这一张牌可以拿走，则将 sum 加 1 。直到 ans < 0 。

题目代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100001], x[100001], y[100001];//数组 a 用来储存每张牌要扣的分数。  
signed main()
{
    int n, ans=0, sum=0;//ans 为累加的分数，sum 为能拿走的牌数
    cin >> n;
    for(int i=1; i <= n; i++){
        cin >> x[i] >> y[i];
        ans += y[i];//累加可以得到的分数
        a[i] += x[i] + y[i];//储存每张牌要扣的分数
    }
    sort(a+1, a+n+1);
    for(int i=1; i <= n; i++){
        if(ans-a[i] >= 0){
            ans -= a[i];//减去
            sum += 1;//这张牌可行，sum 加 1
        } 
        else{
            break;//直接退出，因为后面扣分更多，ans一定也为负数
        }
    }
    cout << sum;
    return  0;
}