[BZOJ1595] [Usaco2008 Jan]人工湖（单调栈）

好难的题。。至少对我来说。

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

#include <cstdio>

#include <iostream>

#define N 100011

#define INF 1000011

#define LL long long

#define min(x, y) ((x) < (y) ? (x) : (y))

int s[N];

int n, p = 1, top;

LL t, sum[N], h[N], w[N], add[N], ans[N];

inline LL read()

{

	LL x = 0, f = 1;

	char ch = getchar();

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';

	return x * f;

}

int main()

{

	int i, l, r;

	n = read();

	h[0] = h[n + 1] = INF;

	for(i = 1; i <= n; i++)

	{

		sum[i] = sum[i - 1] + read();

		h[i] = read();

		if(h[p] > h[i]) p = i;

	}

	for(i = 1; i <= n + 1; i++)

	{

		while(top && h[s[top]] < h[i])

		{

			w[s[top]] = sum[i - 1] - sum[s[top - 1]];

			add[s[top]] = w[s[top]] * (min(h[s[top - 1]], h[i]) - h[s[top]]);

			top--;

		}

		s[++top] = i;

	}

	top = 0;

	l = r = s[++top] = p;

	for(i = 1; i <= n; i++)

	{

		if(h[l - 1] < h[r + 1]) p = --l;

		else p = ++r;

		while(top && h[s[top]] < h[p])

		{

			ans[s[top]] = t + w[s[top]];

			t += add[s[top]];

			top--;

		}

		s[++top] = p;

	}

	for(i = 1; i <= n; i++) printf("%lld\n", ans[i]);

	return 0;

}

巴特西

[BZOJ1595] [Usaco2008 Jan]人工湖（单调栈）

最新文章

热门文章