P9977 [USACO23DEC] Bovine Acrobatics S 题解

· · 题解

解题思路

这道题目代码很短，但是思路很难想。

我们先按照奶牛重量排序，不难想到，最重奶牛一定要放在奶牛塔的最底层，只有这样我们才能保证奶牛数目最大，然后向上搭上第一头满足 w_{top}-w_i\geq k 的奶牛，以此类推。

然后我们就会发现，这就是贪心，于是记录当前的 m 表示这头牛可以搭在多少座塔上，那么我们就可以知道，实际符合要求的放下的奶牛的头数是 \min(m,a_i) 头。

当我们将奶牛搭在塔上后，会有 \min(m,a_i) 个塔的塔顶被修改，也就是说，这几个塔有可能还可以继续搭下一头奶牛，也有可能不可以搭下一头奶牛，所以我们还需要再次统计一下可以搭的塔的数量。

我们又要想想怎么快速统计可以搭的塔的数量。首先，当 m\ge a_i 时有 m-a_i 个塔可以搭奶牛。既然有 \min(m,a_i) 个塔是搭过当前重量的奶牛的，那么我们把这些塔一起处理，如果 w_{top}-w_{i + 1}\geq k，那么这些塔都是可以继续搭奶牛的，如果塔顶连重量较小的奶牛都搭不上，那么我们没有必要再找下去了。

AC CODE:

#include <stdio.h>
#include <algorithm>
struct node {
    int a, b;
} c[200010];
bool cmp(node a, node b) {
    return a.b < b.b;
}
int ans[200010], id = 1;
long long res;
int main() {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &c[i].b, &c[i].a);
    std::sort(c + 1, c + 1 + n, cmp);
    for (int i = 1; i <= n; i++) {
        while (id < i && c[i].b - c[id].b >= k)
            m += ans[id++];
        ans[i] = m < c[i].a ? m : c[i].a; //系统自带的min有点慢
        m -= ans[i], res += ans[i];
    }
    printf("%lld", res);
    return 0;
}