浙江省赛C.Array in the Pocket（贪心+线段树）

题目链接：

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4102

题意：

给出一个长度为n的数组，重排它们，让相同位置的数不同，并且字典序最小

数据范围：

$1 \le n \le 10^5$
$1 \le a_i \le n$

分析：

不可能构造的情况：

有一个数的数量大于$n$的一半

可以构造的情况：

当前位置一定要填$x$，如果后面的坑位数量等于剩余的非$x$数量（线段树维护）
填第一小的数或者第二小的数（set维护）

ac代码：

#include<bits/stdc++.h>

#define ll long long

#define pa pair<int,int>

using namespace std;

const int maxn=1e5+10;

const int maxm=1e7+10;

const int mod=1e9+7;

set<int>se;

pa tree[maxn*4];

int lazy[maxn*4],num[maxn],book[maxn],n;

int see(int x)

{

    set<int>::iterator i=se.begin();

    if(x==2)i++;

    return (*i);

}

void build(int st,int en,int rt)

{

    if(st==en)

    {

        if(num[st])

            tree[rt]=make_pair(n-book[st]*2,st);

        else

            tree[rt]=make_pair(1e9,st);

        return ;

    }

    int md=(st+en)/2;

    build(st,md,rt*2);

    build(md+1,en,rt*2+1);

    tree[rt]=min(tree[rt*2],tree[rt*2+1]);

}

void updata(int l,int r,int x,int st,int en,int rt)

{

    if(r<st||l>en)

        return ;

    if(l<=st&&r>=en)

    {

        tree[rt].first+=x;

        lazy[rt]+=x;

        return ;

    }

    if(lazy[rt])

    {

        tree[rt*2].first+=lazy[rt];

        tree[rt*2+1].first+=lazy[rt];

        lazy[rt*2]+=lazy[rt];

        lazy[rt*2+1]+=lazy[rt];

        lazy[rt]=0;

    }

    int md=(st+en)/2;

    updata(l,r,x,st,md,rt*2);

    updata(l,r,x,md+1,en,rt*2+1);

    tree[rt]=min(tree[rt*2],tree[rt*2+1]);

}

void intit()

{

    memset(lazy,0,sizeof(lazy));

    for(int i=1;i<=n;i++)book[i]=0;

}

void del(int x)

{

    book[x]--;

    if(book[x]==0)se.erase(x);

    updata(1,n,-1,1,n,1);

    updata(x,x,1,1,n,1);

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        intit();

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

        {

            int x;

            scanf("%d",&x);

            book[x]++;

            num[i]=x;

        }

        build(1,n,1);

        if(tree[1].first<0)

        {

            printf("Impossible\n");

            continue;

        }

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

            if(book[i])se.insert(i);

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

        {

            updata(num[i],num[i],1,1,n,1);

            //int g=se(1);

            if(tree[1].first==0)

            {

                printf("%d",tree[1].second);

                del(tree[1].second);

            }

            else

            {

                int g=see(1);

                if(g==num[i])g=see(2);

                printf("%d",g);

                del(g);

            }

            if(i==n)printf("\n");

            else printf(" ");

        }

    }

    return 0;

}

巴特西

浙江省赛C.Array in the Pocket（贪心+线段树）

题目链接：

题意：

数据范围：

分析：

ac代码：

最新文章

热门文章