hdu 5360𞓜多校連合第6場1008貪欲

http://acm.hdu.edu.cn/showproblem.php?pid=5360
Problem Description
The re are 
n soda conventiently labeled by 
1，2，…，n.beta，their best friends，wants to invite some soda to go hiking.The 
i-th soda will go hiking if the total number of soda that go hiking except hi isのless than 
li andのlarger than 
ri.beta will follow the rules below to invite soda one by:
1.he selects a soda not invited before；
2.he tells soda the number of soda who agree to go hiking by now；
3.soda will agree or disagree according to the number he hears.
Note:beta will always tell the truth and soda will agree if and only the number he hears isのless than 
li andのlarger than 
リ、othewise he will disagree.Onece soda agrees to go hiking he will not regret even ft the final total number fails to meet some soda's will.
Help beta design n invitation order that the number of soda who agree to go hiking is maximm.
 
Input
The re are multiple test cases.The first line of input contains an integer 
T，indicating the number of test cases.For each test case:
The first contains an integer 
n 
（1≦n≦105）、the number of soda.The second line constains 
n integers 
l 1,l 2,…，ln.The third line constains 
n integers 
r 1,r 2,…，rn. 
（0≦li≦ri≦n）
It is garanted that the total number of soda in the input doesn't exced 100000.The number of test cases in the input doesn't exceed 600.
 
Output
For each test case，output the maximnumber of soda.The n in the second line output a permutation of 
1,2,…，n denoting the invitation order.If there re multiple solutions，print any of them.
 
Sample Input

   
   
   
   

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

 
Sample Output

   
   
   
   

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

 

/**
hdu5360||     6 1008    
    ：xxx   n    ，   i            (li,ri)  ，    。                 ？
    ：              。       n   li     ，        ，        x ，   
          li>=x     ri  (set  )   。   O(nlogn)
*/
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<set>
using namespace std;
const int maxn=100005;

struct note
{
    int l,r,id;
    bool operator <(const note &other)const
    {
        return l<other.l;
    }
}a[maxn];

int n,num[maxn],flag[maxn];
set<pair<int,int> >st;

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i].l);
            a[i].id=i+1;
        }
        for(int i=0;i<n;i++)
        {
            scanf("%d",&a[i].r);
        }
        sort(a,a+n);
        int x=0;
        memset(flag,0,sizeof(flag));
        for(int i=0;;)
        {
            while(x>=a[i].l&&i<n)
            {
                st.insert(make_pair(a[i].r,a[i].id));
                i++;
            }
            while(((*st.begin()).first<x)&&st.size()>0)st.erase(st.begin());
            if(st.size()==0)break;
            int cnt=(*st.begin()).second;
            num[x++]=cnt;
            flag[cnt-1]=1;
            st.erase(st.begin());
        }
        printf("%d
",x);
        for(int i=0;i<n;i++)
        {
            if(!flag[i])
            {
                num[x++]=i+1;
            }
        }
        for(int i=0;i<n;i++)
        {
            printf(i==n-1?"%d
":"%d ",num[i]);
        }
    }
    return 0;
}