首页 > 代码库 > 【POJ3658】【USACO 2008 Jan Gold】 2.Artificial Lake人工湖 单调栈
【POJ3658】【USACO 2008 Jan Gold】 2.Artificial Lake人工湖 单调栈
人工湖
Time Limit: 1 Sec Memory Limit: 128 MBDescription
夏日那让人喘不过气的酷热将奶牛们的烦躁情绪推到了最高点。最终，FJ
决定建一个人工湖供奶牛消暑之用。为了使湖看起来更加真实，FJ决定将湖的
横截面建成N(1 <= N <= 100,000)个连续的平台高低错落的组合状，所有的平台
从左到右按1..N依次编号。当然咯，在湖中注入水后，这些平台都将被淹没。
平台i在设计图上用它的宽度W_i(1 <= W_i <= 1,000)和高度（你可以理解
为该平台顶离FJ挖的地基的高度）H_i(1 <= H_i <= 1,000,000)来描述的。所有
平台的高度都是独一无二的。湖的边缘可以视为无限高的平台。下面给出了一张
FJ的设计图：
水。水在离开水管后立即下落，直到撞到平台顶或是更早些时候注入的水。然后
，与所有常温下的水一样，它会迅速地流动、扩散。简单起见，你可以认为这些
都是在瞬间完成的。FJ想知道，对于每一个平台，它的顶部是从哪个时刻开始，
与水面的距离至少为1单位长度。
注意：数据不保证答案全部在32位整型变量的范围内。
Input
* 第1行: 1个整数，N
* 第2..N+1行: 第i+1行为2个用空格隔开的整数W_i、H_i，描述了第i个平台
Output
* 第1..N行: 第i行为1个整数，表示平台i的顶到水面的距离从何时开始大于1个单位长度
Sample Input
34 22 76 4
Sample Output
45026
HINT
输入说明:
输入对应了题目中给出的例子，一共有3个平台，FJ选定的注水点在最低的
1号平台上方。
输出说明:
具体过程请参见问题描述中的图。
题解：单调栈，栈中元素高度一定是单调递减的。注意元素池子的宽度。可以1A。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 101000
#define inf 0x3f3f3f3f
using namespace std;
struct Pool
{
long long w;
int h,id;
Pool(long long _w=0,int _h=0,int _id=0):w(_w),h(_h),id(_id){}
}pool[N],stk[N];
int top,n;
long long ans[N],now;
int main()
{
// freopen("test.in","r",stdin);
int i,j,k;
int temp=inf,id;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%lld%lld",&pool[i].w,&pool[i].h);
pool[i].id=i;
if(temp>pool[i].h)temp=pool[i].h,id=i;
}
stk[++top]=pool[id];
stk[0].h=inf;
int l=id,r=id,p;
pool[0].h=pool[n+1].h=inf;
for(int rn=1;rn<=n;rn++)
{
long long add=0;
if(pool[l-1].h<pool[r+1].h)p=--l;
else p=++r;
while(pool[p].h>stk[top].h&&top)
{
stk[top].w+=add;
ans[stk[top].id]=now+stk[top].w;
now+=stk[top].w*(min(pool[p].h,stk[top-1].h)-stk[top].h);
add=stk[top].w;
top--;
}
pool[p].w+=add;
stk[++top]=pool[p];
}
for(i=1;i<=n;i++)printf("%lld\n",ans[i]);
return 0;
}
【POJ3658】【USACO 2008 Jan Gold】 2.Artificial Lake人工湖 单调栈
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。