Hungry Cow (USACO Bronze 2023 February)

一个直观的模拟题。

稍微注意一下，按天模拟是不能通过的，因为T是 $10^{14}$ ，所以我们需要更快速的办法。观察可以发现，送草的事件的次数N是 $10^5$ ，如果按事件来模拟，就快很多了。

具体办法就是依次处理时间递增的送草事件（题目已经按时间顺序排好），跟踪每天早上之后谷仓里的草的数量，然后就可以计算到下一次送草之间的时间，B牛一共会吃掉多少草，累加起来，就得到结果了。

复杂度是 $\mathcal{O}(N)$ 。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;  // 1e5
ll T;   // 1e14
ll d[100005];
int b[100005];
ll ans;
 
int main() {
    scanf("%d %lld", &n, &T);
    for (int i = 0; i < n; i++)
        scanf("%lld %d", &d[i], &b[i]);
    ll amt = 0;
    for (int i = 0; i < n; i++) {
        amt += b[i];
        ll days = i == n-1 ? T+1-d[i] : d[i+1]-d[i];
        ll eaten = min(days, amt);
        ans += eaten;
        amt -= eaten;
    }
    printf("%lld", ans);
    return 0;
}