「LAOI-8」Boundary 题解

· · 题解

考虑到以下两个点：

  2. 我们选择的进行操作 2 的区间必然有一个左端点位于 1，也必然有一个右端点位于 n，令这两个区间为特殊区间。

显然这两个特殊区间要么是同一个，要么必然无交。若无交，当我们决定了这两个特殊区间后，我们在左边和右边都得到了 -10^9，那我们中间这一段可以用 a_l=a_r=-10^9 来使用操作 2 处理。

我们把操作 1,2 的代价分开考虑，在理想状态下，操作 2 至少要产生 n 的代价，上述策略产生了 n+2 的代价，而操作 1 的最小代价由这两个无交的特殊区间产生，我们可以维护一个 pre_i 表示 2\sim i 中 |a_j-a_1| 即操作 1 所需代价的最小值，再维护一个 suf_i 表示 i\sim n-1 中 |a_j-a_n| 的最小值，我们枚举分界点 p，左右各有一个特殊区间，然后求出 pre_{p-1}+suf_{p+1} 的最小值即可。

如果我们无法找到操作 2 能压到 n+2 以下代价的方式，则上述贪心策略是正确的。由于 A 是个排列，如果中间那一段的 |A_l-A_r|=1，那可以通过牺牲操作 1 的 1 点代价来使得操作 2 的代价为 n，此时操作 1 的代价增加 1，操作二的总代价为 n，也就是把 n+2 压成了 n+1，这种特殊情况可以单独拎出来处理，枚举 |A_i-A_j|=1 的数对即可。

然后特判一下直接选 [1,n] 和左右刚好拼起来的情况，时间复杂度 O(n)。

//luogu uid:Anemones 736184
#include<bits/stdc++.h>
#include<ext/rope>
using namespace __gnu_cxx;
#define mp make_pair
#define pb push_back
#define dbg puts("-------------qaqaqaqaqaqaqaqaqaq------------")
#define pl (p<<1)
#define pr ((p<<1)|1)
#define pii pair<int,int>
#define int long long
#define mod 998244353
#define eps 1e-9
#define ent putchar('\n')
#define sp putchar(' ')
using namespace std;
inline int read(){
    char c=getchar(),f=0;int t=0;
    for(;c<'0'||c>'9';c=getchar()) if(!(c^45)) f=1;
    for(;c>='0'&&c<='9';c=getchar()) t=(t<<1)+(t<<3)+(c^48);
    return f?-t:t;
}
inline void write(int x){
    static int t[25];int tp=0;
    if(x==0) return(void)(putchar('0'));else if(x<0) putchar('-'),x=-x;
    while(x) t[tp++]=x%10,x/=10;
    while(tp--) putchar(t[tp]+48);
}
const int N=1e6+10;
int n,ans;
int a[N],b[N];
int pre[N],pi[N],suf[N],si[N];
signed main(){
    int T=read();
    if(T){
        while(T--){
            /*
                1. 左右两个贴在一起了
                2. 中间那段可以特殊处理
                3. 整段可以特殊处理
            */
            n=read(),ans=INT_MAX;
            for(int i=1;i<=n;i++){
                pre[i]=suf[i]=0,pi[i]=0,si[i]=N;
                a[i]=read();
                b[a[i]]=i;
            }
            ans=min(abs(a[1]-a[n])+n,ans);
            suf[n]=pre[1]=INT_MAX;
            for(int i=2;i<=n;i++){
                if(abs(a[i]-a[1])<=pre[i-1]) pre[i]=abs(a[i]-a[1]),pi[i]=i;
                else pre[i]=pre[i-1],pi[i]=pi[i-1];
            }
            for(int i=n-1;i>=1;i--){
                if(abs(a[i]-a[n])<=suf[i+1]) suf[i]=abs(a[i]-a[n]),si[i]=i;
                else suf[i]=suf[i+1],si[i]=si[i+1];
            }
            for(int i=2;i<=n-2;i++){
                ans=min(abs(a[1]-a[i])+abs(a[n]-a[i+1])+n,ans);
                ans=min(pre[i]+suf[i+1]+n+2,ans);
            }
            write(ans),sp;
            for(int i=3;i<=n-2;i++){
                if(a[i]==n) continue;
                int x=min(i,b[a[i]+1]),y=max(i,b[a[i]+1]);
                if(3<=x&&y<=n-2) ans=min(abs(a[x-1]-a[1])+abs(a[y+1]-a[n])+n+1,ans);
            }
            write(ans),ent;
        }
    }
    return 0;
}