P9121 [USACO23FEB] Hungry Cow B

zhlzt · 2023-03-11 18:16:36 · 题解

题目

• 有一位农场主约翰，他有一只饥饿的牛贝西。
• 每一天晚上，如果农场里有至少 1 堆干草，那么贝西吃且仅吃 1 堆干草。
• 有 n 个事件，第 i 个事件表示第 d_i 天早晨约翰搬运了 b_i 堆干草到农场。
• 求第 1\thicksim t 天贝西共吃掉干草堆的数量。

模拟做法

设 sum 为目前农场里剩余干草堆的数量，ans 为目前贝西共吃掉干草堆的数量。

对于每个 i，我们不妨设 pos 为第 d_{i-1}\thicksim d_{i}-1 天贝西共吃掉干草堆的数量，则有 pos=\min(sum,d_i-d_{i-1})，并执行 sum\gets sum-pos 与 ans\gets ans+pos，最后不能忘了执行 sum\gets sum+b_i。

千万要注意，第 d_n\thicksim t 天共吃掉干草堆的数量还没加上，所以最终要输出 ans+\min(sum,t-d_n+1)，而不是直接输出 ans。

代码实现

#include<bits/stdc++.h>
using namespace std;
long long n,t,sum,ans,pos,d[100010],b[100010];
int main(){
    scanf("%lld%lld",&n,&t);
    for(long long i=1;i<=n;i++){
        scanf("%lld%lld",&d[i],&b[i]);
        pos=min(sum,d[i]-d[i-1]);
        sum-=pos,ans+=pos,sum+=b[i];
    }
    printf("%lld",ans+min(sum,t-d[n]+1));
    return 0;
}