P7594 「EZEC-8」Clear Up 题解

· · 题解

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

题面解释

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

Subtask 1

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

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

时间复杂度为 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

结论：

正确性也是显然的。

初始时，可以对每个位置 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;
}