Bovine Acrobatics (USACO Silver 2023 December)

Bovine Acrobatics (USACO Silver 2024 January)

这个题对思考的要求，很多人觉得比T2，T3要难

首先，我们可以发现从单独一个塔的角度来看，是一个贪心的问题，就是按重量顺序，能则放，一定是最优的。

所以我们按这个思路，就可以得到一个一头头牛放的解法，这个可以通过1-11个测试，得到一半多的分，也不错了。

如果要得满分的话，肯定就需要多头牛一起处理（牛的总数量 101810^{18}）。正确的思路如下：

  1. 我们按牛的重量排序，从最重的牛开始考虑，一次性处理所有这 aia_i 头牛。
  2. 对于第一批牛，能放多少头到塔上（此时都是空的）比较容易，就是 min⁡(M,a0)\min(M, a_0)。
  3. 放完这一批后，我们会发现，在 w0+Kw_0 + K 的重量之前，我们能放的牛变少了，变成了 m=M−min⁡(M,a0)m = M - \min(M, a_0)，我们需要维护这个 mm。mm 的定义是当前重量下，有多少个塔可以放牛。也就是说，到 w1w_1 这个重量的时候，能放的牛的数量是 min⁡(m,a1)\min(m, a_1)。
  4. 如果我们能准确维护 mm 这个值，那么把所有重量循环一遍，就能得到最后的结果。
  5. 维护 mm 的办法是：当放下牛到塔上的时候，mm 减去牛的数量；而当新的一次循环，牛的重量变成 wiw_i 时，将 wj+K≥wiw_j + K \geq w_i 之前放下的牛的数量再加回来（因为这些塔又可以再叠放牛了），就可以了。

这样一遍循环就完成了计算，程序简单，但是思路有一些难想。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n, M, k;
struct node {
    int w, a;
    int c;
    bool operator<(const node& o) const {       // descending order
        return w > o.w;
    }
};
vector<node> cows;
ll ans;
 
int main() {
    scanf("%d %d %d", &n, &M, &k);
    for (int i = 0; i < n; i++) {
        int w, a;
        scanf("%d %d", &w, &a);
        cows.push_back({w, a});
    }
    sort(cows.begin(), cows.end());
 
    int last = 0;
    int m = M; 
    for (int i = 0; i < n; i++) {
        while (cows[last].w - k >= cows[i].w) {
            m += cows[last].c;
            last++;
        }
        cows[i].c = min(m, cows[i].a);
        ans += cows[i].c;
        m -= cows[i].c;
    }
 
    printf("%lld\n", ans);
 
    return 0;
}