「Usaco2008 Jan」人工湖O(∩_∩)O 纯属的模拟+栈

 

题目描述

夏日那让人喘不过气的酷热将奶牛们的烦躁情绪推到了最高点．最终，约翰决定建一个人工湖供奶牛消暑之用． 
为了使湖看起来更加真实，约翰决定将湖的横截面建成N(1≤N≤105)个连续的平台高低错落的组合状，所有的平台从 左到右按1到N依次编号．当然咯，在湖中注入水后，这些平台都将被淹没．  
 平台i在设计图上用它的宽度wi(1≤Wi≤1000)和高度（你可以理解为该平台顶离约翰挖的地基的高度）Hi.（1≤Hi≤1000000）来描述的． 
所有平台的高度都是独一无二的．湖的边缘可以视为无限高的平台． 
下面给出了一张约翰的设计图：  
 
按约翰的设想，在坑挖好后，他会以1单位每分钟的速度往最低的那个平台上注水．水在离开水管后立即下落，直到撞到平台顶或是更早些时候注入的水然后，与所有常温下的水一样，它会迅速地流动、扩散．简单起见，你可以认为这些都是在瞬间完成的． 
下图展示了一个样例，样例数据即是本题的所给输入样例。 


约翰想知道，对于每一个平台，它的顶部是从哪个时刻开始，与水面的距离至少为1单位长度． 
注意：数据不保证答案全部在32位整型变量的范围内 

 

输入

第1行:1个整数，N ; 
第2~N+1行:第i+1行为2个用空格隔开的整数Wi、Hi，描述了第i个平台. 

 

输出

输出N行。  
第1~N行: 第i行为1个整数，表示平台i的顶到水面的距离从何时开始大于1 单位长度。 

 

样例输入 

3
4 2
2 7
6 4

 

样例输出

4
50
26

 

解题过程：

• 这题的主要算法就是栈，不得不说用栈搞模拟还挺神奇的。。。
• 这题就是模拟从最低的平台注水，然后将最低的填满以后从最低的平台向两边扩展；
• 每次找最近的最低的平台h，然后将水填到h高度
• 栈里存的是向外扩展的时候，有时会遇到高度递减的情况，这时并不能填水，但要把这些高度都递减（即扩展时的顺序）记录进栈，
• 然后遇到一个比比水面高的平台h时，模拟倒水，水会挨个淹没最低的平台，即需要从栈顶一个一个出战计算淹没时间，直至栈顶平台高度>h，此时h入栈。重复执行就可算出答案

然后就是代码，感觉模拟这个东西就是考码力和思维强度的。。。。

 1 // luogu-judger-enable-o2
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 const int maxn=1e6+10;
 5 const int inf=1<<30;
 6 long long  top;
 7 struct Pool
 8 {
 9     long long w;
10     long long h;
11     long long id;
12     Pool(long long ww=0,long long hh=0, long long _id=0):w(ww),h(hh),id(_id){};
13 }pool[maxn],struck[maxn];
14 long long n,m;
15 long long ans[maxn];
16 long long now;
17 inline long long  read(){
18     register long long  x=0,f=1;char ch=getchar();
19     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
20     while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
21     return (f==1)?x:-x;
22 }
23 int main()
24 {
25     long long temp=inf,id;
26     n=read();
27     for(int i=1;i<=n;i++)
28     {
29         pool[i].w=read();
30         pool[i].h=read();
31         pool[i].id=i;
32         if(temp>pool[i].h)
33         {
34             temp=pool[i].h;
35             id=i;
36         }
37     }
38     struck[++top]=pool[id];
39     struck[0].h=inf;
40     long long l=id;
41     long long r=id;
42     long long p;
43     pool[0].h=pool[n+1].h=inf;
44     for(int i=1;i<=n;i++)
45     {
46         long long add=0;
47         if(pool[l-1].h<pool[r+1].h)
48         {
49             p=--l;
50         }
51         else
52         {
53             p=++r;
54         }
55         while(pool[p].h>struck[top].h&&top)
56         {
57             struck[top].w+=add;
58             ans[struck[top].id]=now+struck[top].w;
59             now+=struck[top].w*(min(pool[p].h,struck[top-1].h)-struck[top].h);
60             add=struck[top].w;
61             top--;
62         }
63         pool[p].w+=add;
64         struck[++top]=pool[p];
65     }
66     for(int i=1;i<=n;i++)
67     {
68         printf("%lld\n",ans[i]);
69     }
70     return 0;
71 }

总结一下：

在想到某些思路时要敢于打，模拟可以用各种各样的方式去优化，然后注意一下一些细节就可以了。