自动搬运

查看原文

来自洛谷，原作者为

	幻·光 这个家伙很菜，什么也没有留下

搬运于2025-08-24 21:43:11，当前版本为作者最后更新于2020-08-07 16:23:25，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本题题意如下图。 图中，两边无限高，而$C$最矮，那么就从$C$开始注水，当水位到达$C$两边最矮的那个平台（也就是$B$）顶部时，就注满了，接着开始$C$出栈，$D$移到$B$右边，然后注$B……$（以此类推）。

那么，实际上就是一个单调递减栈。

如果进栈元素比栈顶高，那么栈内比它矮的都先注满，再出来，累加出栈元素的宽度，实现过程如下图。

那么代码就是下面这样。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+50;
struct pingtai
{
	 long long kuandu;//平台宽度 
	 long long gaodu;//平台高度 
}a[N];
long long ans[N],sta[N][2],tt,temp,minn=100000099,sta1[N];
int main()
{
	long long n,zz=0;
	cin>>n;
	a[0].gaodu=9999999999;//题目说了，两边无限高 
	a[n+1].gaodu=9999999999;//奶牛：我上不来了
	for(long long i=1;i<=n;i++)
	{
		cin>>a[i].kuandu>>a[i].gaodu;
		if(a[i].gaodu<minn)
		{
			minn=a[i].gaodu;//最矮平台
			temp=i;//最矮平台下标 
		}
	} 
	sta1[++tt]=temp;
	long long now=0;//现在所用时间
	long long l=temp-1,r=temp+1;//l:最矮平台左边那个平台的下标；r：最矮平台右边那个平台的下标 
	for(long long i=1;i<=n;i++)
	{
		long long xx,yy;//分别记录高度和宽度
		long long kuan=0;//用来累计宽度
		if(a[l].gaodu<a[r].gaodu)//如果l平台比r平台矮，就该往l平台注水
		{
			xx=a[l].gaodu;
			yy=a[l].kuandu;//统计
			while(tt>0 && a[l].gaodu>a[sta1[tt]].gaodu)//单调递减栈 
			{
				a[sta1[tt]].kuandu+=kuan;
				ans[sta1[tt]]=now+a[sta1[tt]].kuandu;//填满这个地方所需时间就是宽度*1，直接加上宽度就可以了 
				kuan=a[sta1[tt]].kuandu;//加上栈顶宽度 
				now+=(min(a[sta1[tt-1]].gaodu,a[l].gaodu)-a[sta1[tt]].gaodu)*a[sta1[tt]].kuandu;
				tt--;
			}
			a[l].kuandu+=kuan;//进栈平台宽度要加上出栈平台的宽度 
			sta1[++tt]=l;
			l--;//l一直向左移，所以--，r相反 
		} 
		else
		{
			xx=a[r].gaodu;
			yy=a[r].kuandu;//统计
			while(tt>0 && a[r].gaodu>a[sta1[tt]].gaodu)//单调递减栈 
			{
				a[sta1[tt]].kuandu+=kuan;
				ans[sta1[tt]]=now+a[sta1[tt]].kuandu;//填满这个地方所需时间就是宽度*1，直接加上宽度就可以了 
				kuan=a[sta1[tt]].kuandu;//加上栈顶宽度 
				now+=(min(a[sta1[tt-1]].gaodu,a[r].gaodu)-a[sta1[tt]].gaodu)*a[sta1[tt]].kuandu;
				tt--;
			}
			a[r].kuandu+=kuan;//进栈平台宽度要加上出栈平台的宽度 
			sta1[++tt]=r;
			r++; 
		}
	} 
	for(long long i=1;i<=n;i++)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
}