题解：P12675 「LAOI-8」Boundary

· · 题解

题目传送门

思路

考虑贪心。

题目要求求出将序列 A 所有元素均变为 −10^9 的最小代价，可以分类讨论，主要有以下四种情况：

  1. 一次直接将整个区间赋值为 -10^9；
  2. 先将区间的两端赋值为 -10^9，再将整个区间赋值为-10^9；
  3. 将区间分为两段，每段分别赋值为 -10^9；
  4. 将区间分为三段，每段分别赋值为 -10^9；

容易证明，若将区间分为四段及以上，则肯定不如上述的第二种情况。所以只需将四种情况分别讨论，取最优解即可。

如何实现？

设数组 a 为原来的排列，建立另外四个数组 b、c、d、e，其中：

可以通过这五个数组来表示每种情况的花费。

  1. 情况一：花费为 |a[n]-a[1]|+n。
  2. 情况二：花费为 \min \limits^{n-2}_{i=2}{(b[i]+d[i+1]+n+2)}。
  3. 情况三：花费为 \min \limits^{n-2}_{i=2}{(b[i]+c[i+1]+n)}。
  4. 情况四：花费为 \min \limits^{n-2}_{i=2}{(b[i]+d[i+1]+|a[i+1]-a[e[i+1]-1]|+n)}，且应满足 e[i]>i+2。

接下来只需要比较四种情况，取花费最小的即可。

AC CODE

#include<bits/stdc++.h>
using namespace std;
const int N=1000005;
int n;
int a[N],b[N],c[N],d[N],e[N];
int read(){
    int p=1,k=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') p=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        k=k*10+c-'0';
        c=getchar();
    }
    return p*k;
}
int main(){
    int T=read();
    while(T--){
        memset(a,0,sizeof(a));  //多测清空
        memset(b,0,sizeof(b));
        memset(c,0,sizeof(c));
        memset(d,0,sizeof(d));
        memset(e,0,sizeof(e));
        int n=read(),ans=1e9;
        for(int i=1;i<=n;i++){
            a[i]=read();
        }
        for(int i=1;i<=n;i++){   //预处理b、c、d、e四个数组
            b[i]=abs(a[i]-a[1]);
        }
        for(int i=1;i<=n;i++){
            c[i]=abs(a[i]-a[n]);
        }
        d[n]=1e9;
        for(int i=n-1;i>=1;i--){
            if(d[i+1]>c[i]){
                d[i]=c[i];
                e[i]=i;
            }
            else{
                d[i]=d[i+1];
                e[i]=e[i+1];
            }
        }
        ans=min(ans,abs(a[n]-a[1])+n);  //第一种情况
        for(int i=2;i<=n-2;i++){
            ans=min(ans,b[i]+d[i+1]+n+2);  //第二种情况
            ans=min(ans,b[i]+c[i+1]+n);  //第三种情况
            int pos=e[i+1];
            if(pos!=i+1&&pos!=i+2) ans=min(ans,b[i]+d[i+1]+abs(a[i+1]-a[pos-1])+n);  //第四种情况
        }
        printf("%d\n",ans);
    }
    return 0;
}