HDU 5493 Queue （线段树逐个插入）

迈不过友情╰ 2022-07-16 23:37 76阅读 0赞

参考博客：  
[http://blog.csdn.net/hyczms/article/details/48767933][http_blog.csdn.net_hyczms_article_details_48767933]

题目链接：  
[http://acm.split.hdu.edu.cn/showproblem.php?pid=5493][http_acm.split.hdu.edu.cn_showproblem.php_pid_5493]

题目大意：有n个人排队，每个人都有一个身高，每个人记得他前面或者后面可能有x个人比他高（满足一个就行），问能否有一个序列满足给出的条件，如果有，请让字典序最小，

解题思路：从前往后插，给n个位置赋值为0，每个人前面或者后面必须有x个0，找到满足条件的靠前的位置，赋值为其为第几个人，线段树维护区间0的个数，若找不到则无解。

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <numeric>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    
    int ans[100005];
    int tre[100005<<2];
    struct P
    {
        int val;
        int poi;
    };
    
    bool cmp(P p1,P p2)
    {
        return p1.val<p2.val;
    }
    void pushup(int rt)
    {
        tre[rt]=tre[rt<<1]+tre[rt<<1|1];
    }
    
    void build(int l,int r,int rt)
    {
        if(l==r)
        {
            tre[rt]=1;
            return ;
        }
        int m=(l+r)>>1;
        build(l,m,rt<<1);
        build(m+1,r,rt<<1|1);
        pushup(rt);
    }
    void update(int l,int r,int rt,int poi,int add)
    {
        if(l==r)
        {
            ans[l]=add;
            tre[rt]=0;
            return ;
        }
        int m=(l+r)>>1;
        if(poi<=tre[rt<<1]) update(l,m,rt<<1,poi,add);
        else update(m+1,r,rt<<1|1,poi-tre[2*rt],add);
        pushup(rt);
    }
    
    P p[100005];
    
    int main()
    {
        int T,cas=1;
        RI(T);
        while(T--)
        {
            int n;
            RI(n);
            for(int i=0;i<n;i++)
            {
                RII(p[i].val,p[i].poi);
            }
            sort(p,p+n,cmp);
            bool mark=true;
            build(1,n,1);
           // cout<<tre[1]<<" "<<tre[2]<<" "<<tre[3]<<endl;
            for(int i=0;i<n;i++)
            {
                int t=p[i].poi;
                int rem=n-i;
                if(t>=rem)
                {
                    mark=false;
                    break;
                }
                if(n-i-t>t+1) {
                        update(1,n,1,t+1,p[i].val);
                    //cout<<"t+1 = "<<t+1<<endl;
                }
                else {
                       // cout<<"n-i-t+1 = "<<n-i-t+1<<endl;
                        update(1,n,1,n-i-t,p[i].val);
                }
            }
            if(mark)
            {
                printf("Case #%d:",cas++);
                for(int i=1;i<=n;i++)
                    printf(" %d",ans[i]);
                printf("\n");
    
            }
            else printf("Case #%d: impossible\n",cas++);
    
        }
    
        return 0;
    }

[http_blog.csdn.net_hyczms_article_details_48767933]: http://blog.csdn.net/hyczms/article/details/48767933
[http_acm.split.hdu.edu.cn_showproblem.php_pid_5493]: http://acm.split.hdu.edu.cn/showproblem.php?pid=5493