专栏文章

「LAOI-8」Boundary 题解

AAnemonesSolara
P12675题解参与者 14已保存评论 16

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
16 条
当前快照
1 份
快照标识符
@mipimnhq
此快照首次捕获于
2025/12/03 12:37
3 个月前
此快照最后确认于
2025/12/03 12:37
3 个月前
查看原文
考虑到以下两个点：
  1. Al=Ar=−109A_l=A_r=-10^9 时可以使用操作 22。
  2. 我们选择的进行操作 22 的区间必然有一个左端点位于 11，也必然有一个右端点位于 nn，令这两个区间为特殊区间。
显然这两个特殊区间要么是同一个，要么必然无交。若无交，当我们决定了这两个特殊区间后，我们在左边和右边都得到了 −109-10^9，那我们中间这一段可以用 al=ar=−109a_l=a_r=-10^9 来使用操作 22 处理。
我们把操作 1,21,2 的代价分开考虑，在理想状态下，操作 22 至少要产生 nn 的代价，上述策略产生了 n+2n+2 的代价，而操作 11 的最小代价由这两个无交的特殊区间产生，我们可以维护一个 preipre_i 表示 2∼i2\sim i 中 ∣aj−a1∣|a_j-a_1| 即操作 11 所需代价的最小值，再维护一个 sufisuf_i 表示 i∼n−1i\sim n-1 中 ∣aj−an∣|a_j-a_n| 的最小值，我们枚举分界点 pp，左右各有一个特殊区间，然后求出 prep−1+sufp+1pre_{p-1}+suf_{p+1} 的最小值即可。
如果我们无法找到操作 22 能压到 n+2n+2 以下代价的方式，则上述贪心策略是正确的。由于 AA 是个排列，如果中间那一段的 ∣Al−Ar∣=1|A_l-A_r|=1，那可以通过牺牲操作 11 的 11 点代价来使得操作 22 的代价为 nn，此时操作 11 的代价增加 11，操作二的总代价为 nn，也就是把 n+2n+2 压成了 n+1n+1，这种特殊情况可以单独拎出来处理，枚举 ∣Ai−Aj∣=1|A_i-A_j|=1 的数对即可。
然后特判一下直接选 [1,n][1,n] 和左右刚好拼起来的情况，时间复杂度 O(n)O(n)。
CPP
//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;
}

评论

共 16 条评论，欢迎与作者交流。

正在加载评论...