首页 > ACM题库 > HDU-杭电 > HDU 4446-IT Companies-线段树-[解题报告]HOJ
2015
07-16

HDU 4446-IT Companies-线段树-[解题报告]HOJ

IT Companies

问题描述 :

There are N IT companies which are labeled from 1 to N. Each of them has a branch (a branch is not a company, and companies and branches are all called "unit").The branches are labeled from -1 to �CN. The branch of company i is labeled as -i. The number of workers of each company and its branch has to fit the rules below:
1. The number of workers of a company must be larger than that of the branch of it.
2. There are more workers in company i than company j if and only if there are more workers in the branch of company i than the branch of company j.
Among the companies whose label is larger than i(range from i+1 to n),and the branches whose label is larger than -i (range from -1 to �C(i-1) ), there are c[i] units which have more workers than company i.
You need to sort the 2×N units in the ascending order by the number of workers.

输入:

The input contains multiple test cases. Each test case begins with a single line containing one integer N indicating the number of companies (0 < N ≤ 100000). Next line contains N integers which are c[1],c[2]…c[N] (c[i] ≤ N).
The input ends with N = 0.

输出:

The input contains multiple test cases. Each test case begins with a single line containing one integer N indicating the number of companies (0 < N ≤ 100000). Next line contains N integers which are c[1],c[2]…c[N] (c[i] ≤ N).
The input ends with N = 0.

样例输入:

2
1 1
10
4 8 3 4 2 0 5 7 1 6
0

样例输出:

Impossible
-8 -2 -10 -7 8 2 10 -4 7 -1 4 -3 -5 -9 1 3 5 9 -6 6

官方题解

1.一开始开2个队列a,ba为答案队列,b为临时队列

2.找出当最小的C值为C[k](相同时取k最小的)

a)C[k]=0:将k加入a-k加入b。在C序列中删除元素C[k],并将C[1]C[k-1]减一。

b)C[k]>0:将b队首的元素p取出加入a,并将C[-p+1]c[n]减一。

重复做直到所有元素进入a或者b

3.将b接在a后面,倒序就是答案序列

无解有两种情况:

1C中出现了负数。

2.出现2b情况时b为空

#include <iostream>
#include <cstdio>
#include <cstring>
#define ls (t<<1)
#define rs (t<<1|1)
#define midt (tr[t].l+tr[t].r>>1)
using namespace std;
const int maxn=1e5+9;
const int inf=1111111;
int ans[maxn<<1],que[maxn<<1];
int a[maxn];

struct
{
    int l,r,min,lazy,id;
}tr[maxn<<2];

void pushdown(int t)
{
    if(tr[t].lazy)
    {
        tr[ls].min+=tr[t].lazy;
        tr[rs].min+=tr[t].lazy;
        tr[ls].lazy+=tr[t].lazy;
        tr[rs].lazy+=tr[t].lazy;
        tr[t].lazy=0;
    }
}


void maketree(int t,int l,int r)
{
    tr[t].l=l;
    tr[t].r=r;
    tr[t].lazy=0;
    if(l==r)
    {
        tr[t].min=a[l];
        tr[t].id=l;
        return ;
    }
    int mid=midt;
    maketree(ls,l,mid);
    maketree(rs,mid+1,r);
    if(tr[ls].min<=tr[rs].min)
    {
        tr[t].min=tr[ls].min;
        tr[t].id=tr[ls].id;
    }
    else
    {
        tr[t].min=tr[rs].min;
        tr[t].id=tr[rs].id;
    }
}

void modify(int t,int l,int r,int tmp)
{
    if(tr[t].l==l&&tr[t].r==r)
    {
        tr[t].min+=tmp;
        tr[t].lazy+=tmp;
        return ;
    }
    pushdown(t);
    int mid=midt;
    if(r<=mid) modify(ls,l,r,tmp);
    else if(mid+1<=l) modify(rs,l,r,tmp);
    else
    {
        modify(ls,l,mid,tmp);
        modify(rs,mid+1,r,tmp);
    }

    if(tr[ls].min<=tr[rs].min)
    {
        tr[t].min=tr[ls].min;
        tr[t].id=tr[ls].id;
    }
    else
    {
        tr[t].min=tr[rs].min;
        tr[t].id=tr[rs].id;
    }
}

int querymin()
{
//    cout<<tr[1].min<<endl;
    if(tr[1].min==0)
    return tr[1].id;
    else return -1;
}

int main()
{
    int n;
    while(scanf("%d",&n),n)
    {
        int st=1,ed=0,lon=2*n;
        bool flage=1;
        for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
        maketree(1,1,n);
        for(int i=1;i<=n;i++)
        {
            int tmp;
            while(querymin()==-1)
            {
                if(st<=ed)
                {
                    ans[lon--]=-que[st];
                    if(que[st]+1<=n)
                    modify(1,que[st]+1,n,-1);
                    st++;
                }
                else
                {
                    flage=0;
                    break;
                }
            }
            if(!flage) break;
            tmp=querymin();
            ans[lon--]=tmp;
            que[++ed]=tmp;
            if(1<=tmp-1)
            modify(1,1,tmp-1,-1);
            modify(1,tmp,tmp,inf);
        }
        if(!flage)
        {
            printf("Impossible\n");
        }
        else
        {
            while(st<=ed)
            {
                ans[lon--]=-que[st++];
            }
            for(int i=1;i<=n*2;i++)
            printf("%d ",ans[i]);
            printf("\n");
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/yrleep/article/details/9902191