用到优先队列
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<vector> 6 #include<queue> 7 #define N 1000005 8 using namespace std; 9 struct Node 10 { 11 int r,l,id; 12 bool operator <(Node a) const{return l>a.l;}//为了优先队列的优先级的排列，>队列顶端是最小的，反之是最大的 13 }soda[N]; 14 int cmp(Node a,Node b) 15 { 16 return a.r<b.r; 17 } 18 int vis[1000005]; 19 vector<int> ans; 20 priority_queue<Node> que; 21 int main() 22 { 23 int t; 24 cin>>t; 25 while(t--) 26 { 27 int n; 28 cin>>n; 29 memset(vis,0,sizeof(vis)); 30 ans.clear(); 31 while(!que.empty()) que.pop(); 32 for(int i=0;i<n;i++) 33 { 34 cin>>soda[i].r; 35 soda[i].id=i+1; 36 } 37 for(int i=0;i<n;i++) cin>>soda[i].l; 38 sort(soda,soda+n,cmp); 39 int num=0; 40 int id=0; 41 for(int i=0;i<n;i++) 42 { 43 while(id<n) 44 { 45 if(soda[id].r<=num) 46 { 47 que.push(soda[id]); 48 id++; 49 } 50 else break; 51 } 52 while(!que.empty()) 53 { 54 if(que.top().l>=num) 55 { 56 ans.push_back(que.top().id); 57 vis[que.top().id]=1; 58 que.pop(); 59 num++; 60 break; 61 } 62 else que.pop(); 63 } 64 } 65 int cnt = 0 ; 66 int i; 67 printf("%d\n", ans.size()) ; 68 for(i = 0 ; i < ans.size() ; i++) 69 { 70 cnt++ ; 71 if( cnt == n ) 72 printf("%d\n", ans[i]) ; 73 else 74 printf("%d ", ans[i]) ; 75 } 76 for(i = 1 ; i <= n ; i++) 77 { 78 if( vis[i] ) continue ; 79 cnt++ ; 80 if( cnt == n ) 81 printf("%d\n", i) ; 82 else 83 printf("%d ", i) ; 84 } 85 } 86 return 0; 87 88 }