题解 | #魔法雪橇载客赛#

F 魔法雪橇载客赛

前排提醒：这场比赛很多人吃了没看题目分值的亏，分值越小的题目越简单（比如 EFG 题远比 ABC 题简单）。一些选手按照题目原始顺序开题，而 A 题的难度据帆神反映已超过蓝桥杯省赛大部分题目。题目列表的平均分能看到题目的分值。明明蓝桥杯都是按照难度递增排列题目不知道这里为什么这样排

很多选手因为死磕前面的题目爆零或者差点爆零，这种情况也不全是他们的问题。没发挥好的同学也不用太灰心，不论赛时赛后能独立写出 50~75 分的题目省二都稳了。

设 ，，则此时多余的力气为 。根据题意，我们需要控制 ，使其大于等于 。

假设一开始所有的驯鹿都在拉车，则 。将编号为 的鹿放上车， 就减少 。我们尝试逐个地将鹿放上车，每次操作挑选 最小的鹿，使 下降地尽可能慢。直到 不能再 为止。

评测记录

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Luguan {
    int p, w;
    ll s;
    bool operator < (const Luguan& b) const {
        return s < b.s;
    }
};

void solve() {
    int n;
    cin >> n;
    
    vector<Luguan> lu(n + 5);
    ll sump = 0;
    
    for (int i = 1; i <= n; i++) {
        cin >> lu[i].w >> lu[i].p;
        sump += lu[i].p;
        lu[i].s = lu[i].p + lu[i].w;
    }
    
    sort(lu.begin() + 1, lu.begin() + n + 1);
    
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (sump - lu[i].s >= 0) {
            sump -= lu[i].s;
            ans++;
        } else {
            break;
        }
    }
    
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}