自动搬运

查看原文

来自洛谷，原作者为

	BurningEnderDragon 暴力出奇迹，打表出省一

搬运于2025-08-24 22:31:22，当前版本为作者最后更新于2021-05-30 19:22:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目链接：P7594 「EZEC-8」Clear Up

题面解释

清除方法为：在任意一个位置花费一定能量，清除以当前位置为中心的一个金字塔型区域的方块（在每个位置消除的方块数量沿中心向两边递减）。

Subtask 1

当 $n=1$ 时，显然答案为这个位置上的方块数量。

当 $n=2$ 时，显然存在以下几种情况：

• 若两个位置上的方块数量均为 $0$，则不需要进行消除，答案为 $0$；
• 若两个位置上的方块数量相同且不为 $0$ ，则最优的消除方式为在其中任意一个位置花费相当于 $($ 当前位置上的方块数量 $+1)$ 的能量，消除这两个位置上的所有方块，答案为 $($ 任意一个位置上的方块数量 $+1)$；
• 若两个位置上的方块数量不相同，则最优的消除方式为在方块数量较多的位置花费相当于当前位置上的方块数量的能量，消除这两个位置上的所有方块，答案为方块数量较多的位置上的方块数量。

时间复杂度为 $O(1)$

代码（题解篇幅有限）

Subtask 2

结论：对于一个不包含 $0$ 的区间，选择一个位置花费能量消除整个区间一定是最优解。

举例说明：

对于以下这组数据：

8
1 2 3 2 1 1 2 1

可以作出以下图像：

如图所示，有以下两种最优的消除方式：

1. 在位置 $3$ 消耗 $3$ 点能量消除位置 $1 \sim 3$ 的方块（红色区域），在位置 $7$ 消耗 $2$ 点能量消除位置 $6 \sim 8$ 的所有方块（绿色区域）。
2. 在位置 $5$ 消耗 $5$ 点能量消除位置 $1 \sim 8$ 的方块（蓝色区域）。

事实上，第二种消除方式可以覆盖位置 $1 \sim 9$。显然上述结论成立。

对于 Subtask 2，$n \le 10^3$，可以暴力枚举在每个位置花费能量消除所有的方块所需要的能量，时间复杂度为 $O(n^2)$；

对于 Subtask 3，则需要以下的优化技巧。

Subtask 3

结论：若当前选择在位置 $u$ 花费 $w$ 点能量消除一个区间的所有方块，则选择在位置 $u+1$ 花费 $w+1$ 点能量仍然可以消除这个区间的所有方块。

正确性是显然的。

盗一张 pocafup 的图（

做法为初始化 $u=1$，$w=1$，从左到右枚举每个位置 $i$，若当前的 $u$ 和 $w$ 无法消除位置 $i$ 上的所有方块，则令 $u=u+1$，$w=w+1$，直到 $u$ 和 $w$ 可以消除位置 $i$ 上的所有方块，或 $u=i$。若 $u=i$ 时当前的 $u$ 和 $w$ 仍然无法消除位置 $i$ 上的所有方块，则令 $w=a_i$。

时间复杂度为 $O(n)$。

代码（题解篇幅有限）

Subtask 4

结论：

• 对于一个存在 $0$ 的区间，选择一个位置花费能量消除整个区间不一定是最优解。
• 对于两个相邻或相交的区间 $A$ 和 $B$，它们合并后的区间记为 $A \bigcup B$，消除区间 $A$，$B$，$A \bigcup B$ 的所有方块的最小花费记为 $w_A$，$w_B$，$w_{A \bigcup B}$，若 $w_{A \bigcup B} \le w_A + w_B$，则可以合并区间 $A$ 和 $B$。

正确性也是显然的。

初始时，可以对每个位置 $i$ 构造一个单独的区间，区间花费的能量 $w=a_i$，中心位置 $m=i$，左端点 $l=i-(a_i-1)$，右端点 $r=i+(a_i-1)$。

然后暴力枚举任意两个区间判断是否可以合并，即可得出答案。时间复杂度为 $O(n^2)$。

同理，对于 Subtask 5，需要优化合并方式。

Subtask 5

结论：因为每个区间都是金字塔型的，所以对于两个满足 $m_A < m_B$ 的区间，这两个区间可以合并当且仅当 $r_A \le l_B - 2$，即两个区间之间至少间隔 $1$ 个位置。

下面这张图片可以说明问题：

可以建立一个栈来进行合并。

做法如下：

1. 对于每个位置 $i$ ，若 $a_i \not= 0$，则构造一个单独的区间，将其入栈。
2. 每构造完一个区间并入栈后，取出栈顶的两个区间，并尝试合并，若可以合并，则删除栈顶的两个区间，并将合并后的区间入栈，直到栈中只有一个区间或者栈顶的两个区间无法合并。

对于两个区间 $A$ 和 $B$，它们合并后的区间 $A \bigcup B$ 的左端点 $l_{A \bigcup B} = \min(l_A,l_B)$，右端点 $r_{A \bigcup B} = \max(r_A,r_B)$，中心位置 $m_{A \bigcup B} = \dfrac{l_{A \bigcup B} + r_{A \bigcup B}}{2}$，花费的能量 $w_{A \bigcup B} = \left\lceil \dfrac{r_{A \bigcup B} - l_{A \bigcup B}}{2} \right\rceil + 1 = \left\lfloor \dfrac{r_{A \bigcup B} - l_{A \bigcup B} + 3}{2} \right\rfloor$。容易发现，实际计算出的 $m_{A \bigcup B}$ 可能不是整数，但在实现中并不需要处理 $m_{A \bigcup B}$。

由于 $i$ 从左到右扫描，所以可以保证栈中所有区间的中心位置 $m$ 始终单调递增，即使合并后也是如此。所以最终栈中任意的两个区间，一定是不能合并的。

因为区间个数为 $n$，合并最多发生 $n-1$ 次，所以时间复杂度为 $O(n)$。

完整AC代码如下：

#include <cstdio>
#include <stack> 

inline int Min(const int x,const int y)  //据说手写比 STL 快一点 
{
	return x<=y?x:y;
}

inline int Max(const int x,const int y)  //据说手写比 STL 快一点 
{
	return x>=y?x:y;
}

struct Area  //存储一个区间可以覆盖的左右端点 
{
	int left,right;
};

template <typename type>
class Stack  //手写栈，比 STL 常数小，并且操作方便 
{
private:
	static const int STACK_MAX=1000000;
	int head;
	type v[STACK_MAX];
public:
	Stack()  //初始化栈顶指针为 0 
	{
		head=0;
	}
	inline bool empty()  //返回栈是否为空 
	{
		return head==0;
	}
	inline int size()  //返回栈中的元素个数 
	{
		return head;
	}
	inline void push(const type x)  //向栈中插入一个元素 
	{
		v[head++]=x;
		return ;
	}
	inline void pop()  //删除栈顶的元素 
	{
		--head;
		return ;
	}
	inline type top(const int x)  //返回栈顶的元素 
	{
		return v[head-1-x];
	}
};
Stack<Area> st;

int n,a,ans=0;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		scanf("%d",&a);  //还是连数组都不用开 
		if(a)
		{
			st.push(Area{i-(a-1),i+(a-1)});  //初始时，每个方块个数不为 0 的位置可以构造出一个区间，构造出这个区间并将其入栈 
			while(st.size()>1 && st.top(1).right>=st.top(0).left-2)  //栈内至少有两个区间，且栈顶的两个区间相邻或相交，此时可以合并 
			{
				register int l=Min(st.top(0).left,st.top(1).left),r=Max(st.top(0).right,st.top(1).right);
				st.pop();  //栈顶的两个区间出栈 
				st.pop();
				st.push(Area{l,r});  //新区间入栈 
			}
		}
	}
	while(!st.empty())  //统计答案 
	{
		register int l=st.top(0).left,r=st.top(0).right;
		ans+=(r-l+3)/2;  //对于每个区间，计算这个区间花费的能量 
		st.pop();
	}
	printf("%d\n",ans);
	return 0;
}