P2897题解

· · 题解

本题题意如下图。 图中，两边无限高，而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;
}