P9893题解

· · 题解

简述题意

给数列分组，可以一个一组也可以两个一组，两个一组必须要挨着，定义一个组的权值是这个组内所有数字的权值的和，问你所有分组方案中权值最大的组减去权值最小的组得到的值的最小值。

做法

观察到最大值只有 O(n) 种，具体的说是 2n-1 种。

于是考虑枚举最大值，判断能找到的最大的最小值。

找最小值的时候你会规定一些分组不能选，一些分组可以选。

考虑动态规划，f_{i,0/1} 表示考虑到第 i 个数，最后一个数是不是完整的一组。

然后你会发现转移是一个矩阵，分组哪些可以选和不可以选也可以用矩阵的单点修来表示，于是这题就做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,inf=1e18;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
int n,a[N],m;
struct mxr{
    int v,x,op;
}b[N];
struct martix{
    int a00,a01,a10,a11;
    martix operator * (martix a){
        return{
            max(min(a00,a.a00),min(a01,a.a10)),
            max(min(a00,a.a01),min(a01,a.a11)),
            max(min(a10,a.a00),min(a11,a.a10)),
            max(min(a10,a.a01),min(a11,a.a11))
        };
    }
}t[N*4],e[N];
struct martix1{
    int a0,a1;
    martix1 operator * (martix a){
        return{
            max(min(a0,a.a00),min(a1,a.a10)),
            max(min(a0,a.a01),min(a1,a.a11))
        };
    }
}I={inf,inf};
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
void up(int x){
    t[x]=t[ls(x)]*t[rs(x)];
}
void build(int x,int l,int r){
    if(l==r){
        t[x]=e[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls(x),l,mid),build(rs(x),mid+1,r);
    up(x);
}
void update(int x,int st,int ed,int k,int v,int op){
    if(st==ed){
        if(op) t[x].a00=v;
        else t[x].a10=v;
        return;
    }
    int mid=(st+ed)>>1;
    if(k<=mid) update(ls(x),st,mid,k,v,op);
    else update(rs(x),mid+1,ed,k,v,op);
    up(x);
}
void solve(){
    m=0;
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        b[++m]={a[i],i,1};
        e[i]={-inf,inf,-inf,-inf};
    }
    if(n==1||n==2){
        cout<<0<<"\n";
        return;
    }
    for(int i=2;i<=n;i++){
        b[++m]={a[i]+a[i-1],i,0};
    }
    sort(b+1,b+m+1,[](mxr a,mxr b){return a.v<b.v;});
    build(1,1,n);
    int ans=inf;
    for(int i=1;i<=m;i++){
        update(1,1,n,b[i].x,b[i].v,b[i].op);
        ans=min(ans,b[i].v-(I*t[1]).a0);
    }
    cout<<ans<<"\n";
}
signed main(){
    int t=read();
    while(t--) solve();
    return 0;
}