自动搬运

查看原文

来自洛谷，原作者为

	zhlzt Light in the eyes.

搬运于2025-08-24 22:45:32，当前版本为作者最后更新于2023-03-11 18:16:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目

• 有一位农场主约翰，他有一只饥饿的牛贝西。
• 每一天晚上，如果农场里有至少 $1$ 堆干草，那么贝西吃且仅吃 $1$ 堆干草。
• 有 $n$ 个事件，第 $i$ 个事件表示第 $d_i$ 天早晨约翰搬运了 $b_i$ 堆干草到农场。
• 求第 $1\thicksim t$ 天贝西共吃掉干草堆的数量。
• $1\le n\le 10^{5}$，$1\le t\le10^{14}$，$1\le d_i\le 10^{14}$，$1\le b_i\le 10^{9}$。
• $1\le d_1<d_2<\cdots<d_n\le 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;
}