Bovine Acrobatics

题意

有 $N$ 种不同重量的奶牛，第 $i$ 种重量是 $w_i$ ，数量是 $a_i$ 。

现在最多可以搭 $M$ 座塔。一座塔从上到下相邻两头牛必须满足：下面那头牛的重量至少比上面那头牛大 $K$ 。

每头牛最多使用一次，问最多有多少头牛可以出现在某座合法的塔中。

思路

先看一个小数据朴素模拟。它把每头牛都展开出来，从重到轻逐头尝试放入当前最容易满足条件的塔。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 18:53
 * update_at: 2026-07-11 18:56
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll INF = 4000000000000000000LL;

int n;
ll m, k;
vector<ll> cows;    // 小数据下展开后的所有奶牛重量
deque<ll> towers;   // 每座塔当前最上方奶牛的重量

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

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        ll w, a;
        cin >> w >> a;
        for (ll j = 1; j <= a; j++) {
            cows.push_back(w);
        }
    }

    // 朴素做法：逐头处理奶牛，只适合总奶牛数较小的测试。
    sort(cows.begin(), cows.end(), greater<ll>());

    ll tower_cnt = min(m, (ll)cows.size());
    for (ll i = 1; i <= tower_cnt; i++) {
        towers.push_back(INF);
    }

    ll ans = 0;
    for (int i = 0; i < (int)cows.size(); i++) {
        ll w = cows[i];
        if (!towers.empty() && w + k <= towers.front()) {
            towers.pop_front();
            towers.push_back(w);
            ans++;
        }
    }

    cout << ans << '\n';

    return 0;
}

暴力的瓶颈很明显： $a_i$ 可能达到 $10^9$ ，不能真的把所有奶牛展开。

满分做法保留同样的贪心，但把“奶牛”和“塔”都按数量压缩。

先把所有重量按从大到小排序。处理重量为 w 的一组奶牛时，当前所有塔的顶部重量也按从大到小排在一个双端队列里。队首是顶部最重的一批塔。

如果当前奶牛能放到某座塔上，那么它一定能放到队首那批“顶部最重”的塔上。因为队首都不满足 $w + K <= top$ 时，后面的塔顶部只会更轻，更不可能满足。

于是对每一组 (w, a)：

令 $remaining = a$ ，表示还有多少头这种重量的牛没放入塔；
不断从队首拿出满足 $w + K <= top$ 的塔，批量放入当前重量的牛；
实际放入了 $placed = a - remaining$ 头牛；
这些塔的新顶部都变成 w，于是把 (w, placed) 加到队尾。

一开始有 $M$ 座空塔。空塔可以看成顶部重量为无穷大，所以用 (INF, M) 初始化队列。

因为重量是从大到小处理的，每次新产生的顶部重量也越来越小，所以队列始终保持从大到小的顺序。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 18:53
 * update_at: 2026-07-11 18:56
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 200005;
const ll INF = 4000000000000000000LL;

struct CowGroup {
    ll w;   // 重量
    ll cnt; // 这种重量的奶牛数量
};

int n;
ll m, k;
CowGroup cow[MAXN];
deque<CowGroup> tower; // 每组表示若干座当前顶部重量相同的塔

bool cmp_cow(CowGroup a, CowGroup b) {
    return a.w > b.w;
}

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

    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> cow[i].w >> cow[i].cnt;
    }

    sort(cow + 1, cow + n + 1, cmp_cow);

    // 空塔可以看成顶部有一个无穷重的虚拟奶牛。
    tower.push_back((CowGroup){INF, m});

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        ll w = cow[i].w;
        ll remaining = cow[i].cnt;

        // 当前重量的奶牛只能放到顶部重量至少为 w + k 的塔上。
        while (!tower.empty() && remaining > 0 && w + k <= tower.front().w) {
            ll use = min(remaining, tower.front().cnt);
            remaining -= use;
            tower.front().cnt -= use;

            if (tower.front().cnt == 0) {
                tower.pop_front();
            }
        }

        ll placed = cow[i].cnt - remaining;
        if (placed > 0) {
            tower.push_back((CowGroup){w, placed});
            ans += placed;
        }
    }

    cout << ans << '\n';

    return 0;
}

复杂度

排序需要 $O(N \log N)$ 。

每个重量段最多入队一次、出队一次，队列部分是 $O(N)$ 。

总时间复杂度为 $O(N \log N)$ ，空间复杂度为 $O(N)$ 。

总结

本题的关键是不要被“每头牛搭塔”带偏，而是把相同重量的牛批量处理。

从重到轻贪心时，当前奶牛若能放入某座塔，就优先消耗顶部最重的塔；用双端队列维护压缩后的塔顶部数量段，就能把逐头模拟变成按重量段批量模拟。

目录

题意

思路

代码

复杂度

总结