Hungry Cow

题意

FJ 会在若干天的早上送来草包。每天晚上，如果仓库里还有草包，Bessie 就吃掉一个。

给定前 T 天内每次送草的日期和数量，求 Bessie 在第 1 天到第 T 天一共吃掉多少个草包。

思路

暴力想法

最直接的做法是逐日模拟：每天早上加入当天送来的草包，晚上如果仓库不空就吃一个。

这个做法完全贴合题意，适合小数据理解：

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/**
 * 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 13:03
 * update_at: 2026-07-11 13:08
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;

int n;
long long T;
long long day_arr[MAXN];
long long bale_arr[MAXN];

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

    cin >> n >> T;
    for (int i = 1; i <= n; i++) {
        cin >> day_arr[i] >> bale_arr[i];
    }

    long long remain = 0;
    long long answer = 0;
    int pos = 1;

    // 暴力直接逐日模拟，只适合 T 很小的数据。
    for (long long day = 1; day <= T; day++) {
        if (pos <= n && day_arr[pos] == day) {
            remain += bale_arr[pos];
            pos++;
        }

        if (remain > 0) {
            remain--;
            answer++;
        }
    }

    cout << answer << '\n';

    return 0;
}

但是 $T$ 最大到 $10^{14}$ ，逐日循环一定会超时。

按送草日期扫描

观察相邻两次送草之间没有新的事件发生。假设当前剩余 remain 个草包，距离下一次送草还有 days 天，那么这段时间能吃掉：

\min(remain, days)

如果草包不够，就把已有草包吃完；如果草包足够，就每天吃一个，吃满 days 天。

因此不需要逐日模拟，只要按送草日期扫描：

text

1
2
3
4eat = min(remain, days)
answer += eat
remain -= eat
remain += 本次送来的草包

为了统一处理最后一次送草到第 T 天之间的区间，可以在第 T+1 天加一个数量为 0 的哨兵送草。这样最后一段也会被同一套逻辑结算。

代码

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/**
 * 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 13:03
 * update_at: 2026-07-11 13:08
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n;
long long T;
long long day_arr[MAXN];
long long bale_arr[MAXN];

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

    cin >> n >> T;
    for (int i = 1; i <= n; i++) {
        cin >> day_arr[i] >> bale_arr[i];
    }

    // 哨兵交货日，用来统一处理最后一次交货到第 T 天的吃草过程。
    day_arr[n + 1] = T + 1;
    bale_arr[n + 1] = 0;

    long long remain = 0;      // 当前仓库里还剩多少草包。
    long long answer = 0;      // 前 T 天实际吃掉的草包数。
    long long last_day = 1;    // 上一次开始统计吃草的日期。

    for (int i = 1; i <= n + 1; i++) {
        long long days = day_arr[i] - last_day;
        long long eat = min(remain, days);

        answer += eat;
        remain -= eat;

        remain += bale_arr[i];
        last_day = day_arr[i];
    }

    cout << answer << '\n';

    return 0;
}

复杂度

每次送草只处理一次，时间复杂度为 $O(N)$ 。

保存送草日期和数量，空间复杂度为 $O(N)$ 。

所有日期、草包数量和答案都可能达到 $10^{14}$ 量级，需要使用 long long。

总结

这题的关键是把“每天吃一个”的过程压缩成区间结算。

相邻两次送草之间，唯一需要知道的是当前剩余草包数和区间长度，所以每段用一次 min(remain, days) 就能统计吃掉多少。

目录

题意

思路

暴力想法

按送草日期扫描

代码

复杂度

总结