自动搬运

查看原文

来自洛谷，原作者为

	EternalRegrets Glass shatters, but memories linger. Let them cut me open—I’ll forge a new world from the shards.

搬运于2025-08-24 22:40:26，当前版本为作者最后更新于2023-02-09 22:30:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P8586 题解

本题目是一道贪心题。

由题意可知，第 $n$ 天仅可以处理第 $n-1$ 天与第 $n$ 天的陨石。

可以很简单地证明在第 $i$ 天优先处理第 $i-1$ 的陨石会更优一些。因为如果第 $i$ 天优先处理第 $i-1$ 天的陨石，可以让第 $i+1$ 天需要处理的陨石质量减少到最小值，同时也确保了最多处理的陨石质量。

用一个桶去记录每天的陨石质量。

最后循环寻找答案。（特殊处理 $0$ 时刻和最大天数 +$1$）

具体见代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int maxn=0; //天数
int ans=0; //答案
int used; //本天已经打掉的质量
int a[500005]; //桶，记录每天有多少质量的陨石

signed main()
{
	int n; cin>>n;
	int k; cin>>k; //输入
	
	for (int i=1;i<=n;i++)
	{
		int d; cin>>d; //天数
		int m; cin>>m; //质量
		
		a[d]+=m; //桶
		maxn=max(maxn,d); //计算最大天数
	}
	
	for(int i=0;i<=maxn+1;i++) //maxn+1 天需处理 因为 maxn+1 天也可以抵挡 maxn 天的；0 时刻也需处理
	{
		if(i==0) //如果是0时刻
		{
			if(a[i]<k) //如果还没有达到上限
			{
				ans+=a[i];
				a[i]=0;  //归零
			}
			else //如果达到了上限
			{
				ans+=k;
				a[i]-=k;  //打掉可以打的数量
			}
		}
		else
		{
			if(a[i-1]<=k) //看前一天的
			{
				ans+=a[i-1];
				used=a[i-1];
				a[i-1]=0;   //归零
			}
			else
			{
				ans+=k;
				used=k;
				a[i-1]-=k;  //打掉可以打的质量
				continue;
			}
			
			if(a[i]<=k-used) //如果本天的还可以抵挡
			{
				ans+=a[i];
				a[i]=0;
			}
			else //还不可以就挑部分抵挡
			{
				ans+=k-used;
				a[i]=a[i]-k+used;
			}
		}
	}
	
	cout<<ans; //输出
	return 0;
}