自动搬运

查看原文

来自洛谷，原作者为

	QQQfy **

搬运于2025-08-24 21:23:42，当前版本为作者最后更新于2018-06-28 22:06:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

闲聊

本蒟蒻的第一篇题解

这道题一开始死活想不出后来在物理课上想出来的，激动了好久。。。

一查题解好像没有一样的 又激动了好久。。。

咳咳。。进入正题————

算法介绍

1.变量定义与读入

int n,//n个数
a[11000],//存每一根柱子的高度
l,r，//这左和右是代表着啥？一会再讲嘿嘿。。
ans=0;//总积水面积，初始为0
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];

2.去掉首尾的前导0和后缀0方便之后处理。

上文中的l,r表示的其实是有可能积水的有效总区间（包括两头的柱子），l从1起向后找，r从n起向前找。
这个比较easy，直接放本段代码：

l=1;while (a[l]==0) l++;

r=n;while (a[r]==0) r--;

3.找到会积水的各个区间并求和（重点！！！）

我们知道，如果一根柱子后面那根柱子比它低，那么这根柱子与后面的某根柱子就有可能积水；

那么问题来了：怎么求“那根柱子”呢？

好问题！

定义：两柱之间有且只有一个连续区间能盛水，这样的两柱与其之间的所有柱子及空间称为“一个能盛水的容器”。

你想啊，一个能盛水的容器的竖直截面大致形状是怎么样的？两边高四周低！（这不是废话吗。。。） 那么！中间的柱子由于比两端低，就可以抽象成是不存在的（事实上并非如此，一会会分析）。

于是，一个能盛水的容器就只有三种了：

1.左柱子低而右柱子高的；

2.左右柱子一样高的；

3.左柱子高而右柱子低的；

（因为中间的柱子无论多高都比左右两柱低，要不然这个容器里就有两个地方可以装水，也就是两个容器，这与“一个能盛水的容器”相悖）

好！这样的话问题就被分解成了三个子问题：

找到这三种容器，并将它们所能装水的总和作为答案输出即可。

那该怎么求呢？

规定：j为目前的左柱子的下标，k为目前的右柱子的下标

其实一二两种容器可以一起考虑。

开始将j定为l,k定为l+1（为什么是l和l+1？看上文！），不断k++，直到找到第一个右柱子大于等于左柱子的（也就是a[k]>=a[j]），计算这时这个容器内能装水的总量，加进ans里。这样就找到了第一个第一（二）种容器，并且区间[l,k)内将不存在第一二种容器。为什么k那里是开区间呢？因为第k根柱子还有可能是下一个第一二种容器的左柱子。

那么怎么计算这个容器内的积水总量呢？

上文提到，容器之中的柱子事实上不能视做不存在的，因为这些柱子也占了空间。（自己手画一个容器就知道以下公式是怎么推出的了）

ans+=min(a[j],a[k]) * (k-j-1) - 中间柱子总空间（定义为tmp）//前面的那个乘积式实际上是个矩形，你要是画了图的话一下就能发现。只要在每次推进k时tmp+=当前a[k]，就能同时算出tmp，减小了复杂度。

到此，我们终于结束了第一个容器，这时就要来看看接下来的了。 其实只要j=k;k++;重新更新左柱子和右柱子的下标，搜索后面的部分，直到k比r大为止。

以下是第一二种容器的求法。

int tmp=0,j=l,k=l+1;
while (k<=r+1)
	if (a[k]<a[j])
	{
		tmp+=a[k];
		k++;
	}
	else
	{
		ans+=(k-j-1)*a[j]-tmp;//公式
		tmp=0;//记得刷新成0便于以后再记录
		j=k;
		k++;
	}

规定：j为目前的右柱子的下标，k为目前的左柱子的下标//改过了哦

那么第三种容器如何求？如果仍按上面的循环顺序，将不能判断出正确的区间（可以用7 5 2 4 5 1 6模拟看看）

这时我们可以使用倒序的技巧。

如果从后往前搜，那么左柱子高于右柱子的情况就变成了右柱子高于左柱子的情况。

（这或许有些难理解？对搜索来说，实际上没有左右，只有先后之分，从后开始按上面的方法搜，第一个搜到的区间对搜索来说和上面一样，是前面的柱子低于后面的柱子，而由于是倒搜，前柱子实际上是右柱子，后柱子实际上是左柱子，也即：左柱子高于右柱子。只是为了避免重复，这个倒搜中k--及tmp+=a[k]（倒搜嘛）的条件应改为a[k]<=a[j]）

于是第一二种容器的循环基本复制一遍。。。

	tmp=0;j=r;k=r-1;//倒搜嘛
	while (k>=l-1)
		if (a[k]<=a[j])//注意条件
		{
			tmp+=a[k];
			k--;
		}
		else
		{
			ans+=(j-k-1)*a[j]-tmp;
			tmp=0;
			j=k;
			k--;//倒搜！逆推进！
		}

最后输出答案即可。

4.正确性分析

由于所有能装水的容器有且只有这三种，正搜只找到并找全了一二两种，而倒搜时只找到并找全了第三种，故它们的和即为答案，不会重复，不会遗漏，完美！

5.完整代码

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
	int n,a[11000],l,r,ans=0;
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i];
	//去0
	l=1;while (a[l]==0) l++;
	r=n;while (a[r]==0) r--;
	//正搜
	int tmp=0,j=l,k=l+1;
	while (k<=r+1)
		if (a[k]<a[j])
		{
			tmp+=a[k];
			k++;
		}
		else
		{
			ans+=(k-j-1)*a[j]-tmp;
			tmp=0;
			j=k;
			k++;
		}
	//倒搜
	tmp=0;j=r;k=r-1;
	while (k>=l-1)
		if (a[k]<=a[j])
		{
			tmp+=a[k];
			k--;
		}
		else
		{
			ans+=(j-k-1)*a[j]-tmp;
			tmp=0;
			j=k;
			k--;
		}
	cout<<ans;
	return 0;
}

6.时间复杂度

由于根本没有二重循环，循环体也相对简单，时间复杂度O(3n)=O(n)，事实证明，我是全部0ms过的。

7.心灵鸡汤

当从起点看去遥遥无期时，从终点看去可能触手可及！

不仅在OI里，更在生活中！

与大家共勉！