AcWing 4908. 饥饿的牛

AcWing 4908. 饥饿的牛

4908. 饥饿的牛 - AcWing题库

贝茜是一头饥饿的牛。

每天晚上，如果牛棚中还有干草的话，贝茜都会吃掉其中的一捆。

初始时，牛棚中没有干草。

为了让贝茜不被饿死，农夫约翰制定了$N$个给贝茜送干草的计划。

其中第$i$个计划是在第$d_i$天的白天给贝茜送去$b_i$捆干草。

这些计划互不冲突，保证$1 \le d_1 < d_2 < \cdots < d_N \le T$。

请你计算，贝茜在第$1 \sim T$天中有多少天有干草吃。

输入格式

第一行包含两个整数$N$和$T$。

接下来$N$行，每行包含两个整数$d_i, b_i$。

输出格式

输出贝茜在第$1 \sim T$天中有干草吃的天数。

数据范围

输入样例1：

1
2
1 5
1 2

输出样例1：

1
2

样例1解释：

两捆干草在第$1$天早上被送到了牛棚，所以贝茜第$1, 2$天有干草吃。

输入样例2：

1
2
3
2 5
1 2
5 10

输出样例2：

1
3

样例2解释：

两捆干草在第$1$天早上被送到了牛棚，所以贝茜第$1, 2$天有干草吃。

$10$捆干草在第$5$天早上被送到了牛棚，所以贝茜第$5$天有干草吃。

输入样例3：

1
2
3
2 5
1 10
5 10

输出样例3：

1
5

样例3解释：

$10$捆干草在第$1$天早上被送到了牛棚，所以贝茜第$1 \sim 5$天都有干草吃。

题解

我的题解

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
#include <iostream>
using namespace std;

const int N = 100010;
long long n, T;
long long d[N], b[N];

int main()
{
    cin >> n >> T;
    for (long long i = 0; i < n; i ++)
        cin >> d[i] >> b[i];
    // 避免边界问题，在数组的最后加上一组数据
    d[n] = T;
    b[n] = 0;

    long long sum = 0;
    long long res = 0;
    // 遍历每一次送草
    for (long long i = 0; i < n; i ++)
    {
        // 这一次送草为curr
        long long curr = i;
        // 下一次送草为next
        long long next = i + 1;
        // 当前共有sum捆草
        sum += b[curr];
        // cout << sum << endl;
        // 如果现有的草能够吃到下一次送草
        if (sum >= d[next] - d[curr])
        {
            // 加上天数
            res += d[next] - d[curr];
            sum -= d[next] - d[curr];
        }
        // 否则不够，草会吃完，加上草的数量即可
        else
        {
            res += sum;
            // 将草的数量清零
            sum = 0;
        }
        // cout << d[i] << ' ' << b[i] << endl;
    }
    // 如果到了最后一天还有草
    if (sum)
    {
        // 那么最后一天还有得吃
        res ++;
    }
    cout << res << endl;
    return 0;
}

y总题解

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int main()
{
    int n;
    LL T;

    scanf("%d%lld", &n, &T);

    LL res = 0, cur = 0, last = 0;
    for (int i = 1; i <= n; i ++ )
    {
        LL d, b;
        scanf("%lld%lld", &d, &b);
        LL len = d - 1 - last;
        LL days = min(len, cur);

        res += days;
        cur = cur - days + b;
        last = d - 1;
    }

    res += min(cur, T - last);
    printf("%lld\n", res);
    return 0;
}