Poj 3658 Artificial Lake（模拟）

题目地址：http://poj.org/PRoblem?id=3658

思路：记录每一个平台未被淹没的前一个平台与后一个平台。每次选择一个高度最小的坑，填满。并更新其前后平台，即nt[pre[k]]=nt[k]（该平台k被淹没后其前驱平台的后继即为该平台后继平台），pre[nt[k]]=pre[k]（该平台被淹没后其后继平台的前驱即为该平台的前驱），ans[k]=当前水量+淹没该平台的宽度（w[k]）。将该平台淹没的水量为：（1）若该平台的前驱高度小于其后继平台，则将该坑填满的水量即为当前平台宽度*（前驱平台高度-当前平台高度）（通时将其前驱平台宽度加上当前平台宽度）。（2）否则将该坑填满所需水量为当前平台宽度*（后继平台高度-当前平台高度）（通时将其后继平台宽度加上当前平台宽度）。

#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>using namespace std;typedef long long LL;const int maxn=1e5+50;const LL INF=0x3f3f3f3f3f3f3f3f;int n;LL ans[maxn];LL w[maxn],h[maxn];int pre[maxn],nt[maxn];int main(){    int k;    scanf("%d",&n);    w[0]=w[n+1]=1;    h[0]=h[n+1]=INF;    LL tot=0,tmp=INF;    for(int i=1; i<=n; i++)    {        scanf("%lld%lld",&w[i],&h[i]);        pre[i]=i-1,nt[i]=i+1;        if(h[i]<tmp)        {            tmp=h[i];            k=i;        }    }    for(int i=1; i<=n; i++)    {        while(h[pre[k]]<h[k]||h[nt[k]]<h[k])        {            if(h[pre[k]]<h[k]) k=pre[k];            else k=nt[k];        }        nt[pre[k]]=nt[k];        pre[nt[k]]=pre[k];        ans[k]=tot+w[k];        if(h[pre[k]]<h[nt[k]])        {            tot+=w[k]*(-h[k]+h[pre[k]]);            w[pre[k]]+=w[k];            k=pre[k];        }        else        {            tot+=w[k]*(-h[k]+h[nt[k]]);            w[nt[k]]+=w[k];            k=nt[k];        }    }    for(int i=1; i<=n; i++)        printf("%lld/n",ans[i]);    return 0;}