题意：
给定N个无序区间。
对合法区间的定义是：
在这个区间之前已经选出了至少l个合法区间，最多选出了r个合法区间。则该区间为合法区间。
输出最多能挑选出多少个合法区间，并输出合法区间的数量。
思路：
先对原来给定的区间按照l从小到达排序。
然后从选了0个合法区间开始，每次在队列中加入l小于等于之前已选合法区间数的区间加入队列， 按照r从小到大进行优先排列。每次从队列中拿出top，当拿出的区间r小于已经找到的区间数时，我们把他放到临时数组里边。每次选出一个合法区间就更新一下队列的成员，将l小于等于当前合法数的都加入队列。直到无法加入并且队列为空停止循环。
最后输出的数字有三部分，包括没有加入队列的，加入队列但是r值较小变成非法区间的和按照一定次序加入队列的。
注意输出格式。
/************************************************************************* > File Name: D.cpp > Author: ttpond > Created Time: 2015-8-22 16:40:42 ************************************************************************/ #include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<math.h> #include<vector> #include<map> #include<queue> #include<stack> #include<set> using namespace std; struct st { int l,r,id; }; st tree[100010]; bool ccmp(st a,st b) { return a.l<b.l; } struct cmp { bool operator()(const st &a,const st &b) { return a.r>b.r; } }; int main() { int t,tt; scanf("%d",&t); for(tt=0;tt<t;tt++) { int n; priority_queue<st,vector<st>,cmp>q; //priority_queue<st,vector<st>,ccmp>s; scanf("%d",&n); for(int i=0;i<n;i++) { tree[i].id=i+1; } for(int i=0;i<n;i++) { scanf("%d",&tree[i].l); } for(int i=0;i<n;i++) { scanf("%d",&tree[i].r); } sort(tree,tree+n,ccmp); //for(int i=0;i<n;i++) //{ // printf("%d %d %d ",tree[i].l,tree[i].r,tree[i].id); //} // int a; //while(1) // scanf("%d",&a); vector<int>tmpp; vector<int>v; vector<int>::iterator it; int sst=0; int num=0; st tmp; bool ok; for(;num<n||(!q.empty());) { ok=0; while(num<n&&tree[num].l<=sst) { q.push(tree[num]); num++; ok=1; } if((!ok)&&q.empty()) {break;} ok=0; while(!q.empty()) { tmp=q.top(); q.pop(); if(tmp.r>=sst) { sst++; v.push_back(tmp.id); ok=1; break; } tmpp.push_back(tmp.id); } if(!ok) {break;} } ok=0; printf("%d ",v.size()); for(it=v.begin();it!=v.end();it++) { if(it!=v.begin()) printf(" %d",*it); else { ok=1; printf("%d",*it); } } int ttt=234; for(;num<n;num++) { if((!ok)&&ttt==234) { ok=1; printf("%d",tree[num].id); ttt++; } else { printf(" %d",tree[num].id); } } //int a; //while(1) //{ // scanf("%d",&a); //} for(it=tmpp.begin();it!=tmpp.end();it++) { if((!ok)&&it==tmpp.begin()) { printf("%d",*it); } else { printf(" %d",*it); } } printf(" "); } }