zoj 5823 Soldier Game 2018 青岛 I

题意：现在有n个人，现在可以把这n个人分成若干组，只有连续的人才能被分为一组，并且一个组内最多2个人，现在问你所有组内的最大值-最小值这个差值最小是多少。

题解：

将每个人的情况3种情况都拿出来，把这些所有的情况从小到大排序，然后我们枚举起点，然后一直不停的添加线段，然后直到当前的区间内的所有线段，我们可以选择其中的一部分，使得这些线段能够不重合的前提下巧好覆盖1-n的区间内。

tree[x] 假设管理的区间为 [l, r] tree[x][i][j] i代表的是左端点 j 代表的是右端点，当i == 1 的时候，j == 1的时候，我们管理的是 [l+1,r+1]这个区间的状态 i == 0，j == 0 管理的是 [l, r]这个区间的状态。

所以我们pushup的时候不重合的搞就好了。

代码：

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL mod =  (int)1e9+;

const int N = 1e5 + ;

int a[N][];

pll p[N<<];

bool cmp(pll & x, pll & y){

    return a[x.fi][x.se] < a[y.fi][y.se];

}

int tree[N<<][][];

void Build(int l, int r, int rt){

    tree[rt][][] = tree[rt][][] = tree[rt][][] = tree[rt][][] = ;

    if(l == r) {

        tree[rt][][] = ;

        return ;

    }

    int m = l+r >> ;

    Build(lson); Build(rson);

}

void PushUp(int rt){

    tree[rt][][] = (tree[rt<<][][] && tree[rt<<|][][]) || (tree[rt<<][][] && tree[rt<<|][][]);

    tree[rt][][] = (tree[rt<<][][] && tree[rt<<|][][]) || (tree[rt<<][][] && tree[rt<<|][][]);

    tree[rt][][] = (tree[rt<<][][] && tree[rt<<|][][]) || (tree[rt<<][][] && tree[rt<<|][][]);

    tree[rt][][] = (tree[rt<<][][] && tree[rt<<|][][]) || (tree[rt<<][][] && tree[rt<<|][][]);

}

void Update(int L, int op,int l, int r, int rt){

    if(l == r){

        tree[rt][][op] ^= ;

        return ;

    }

    int m = l+r >> ;

    if(L <= m) Update(L, op, lson);

    else Update(L, op, rson);

    PushUp(rt);

}

int main(){

    int T, n;

    scanf("%d", &T);

    while(T--){

        scanf("%d", &n);

        int m = ;

        for(int i = ; i <= n; ++i){

            scanf("%d", &a[i][]);

            p[++m] = pll(i,);

            if(i-) {

                a[i-][] = a[i-][] + a[i][];

                p[++m] = pll(i-,);

            }

        }

        sort(p+, p++m, cmp);

        Build(,n,);

        LL ans = INF;

        for(int i = , j=; i <= m; ++i){

            while(j <= m && !tree[][][]){

                Update(p[j].fi, p[j].se, , n, );

                j++;

            }

            if(tree[][][]) ans = min(ans, 1ll*a[p[j-].fi][p[j-].se] - a[p[i].fi][p[i].se]);

            Update(p[i].fi, p[i].se, , n, );

        }

        printf("%lld\n", ans);

    }

    return ;

}

巴特西

zoj 5823 Soldier Game 2018 青岛 I

最新文章

热门文章