HikingTime Limit: 6000/3000 MS (Java/Others)Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 492Accepted Submission(s): 263Special Judge
Problem Description
There aresoda conveniently labeled by. beta, their best friends, wants to invite some soda to go hiking. The-th soda will go hiking if the total number of soda that go hiking except him is no less thanand no larger than. beta will follow the rules below to invite soda one by one: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 if the number he hears is no less thanand no larger than, otherwise he will disagree. Once soda agrees to go hiking he will not regret even if the final total number fails to meet some soda’s will.Help beta design an invitation order that the number of soda who agree to go hiking is maximum.
Input
There are multiple test cases. The first line of input contains an integer, indicating the number of test cases. For each test case:The first contains an integer, the number of soda. The second line constains. The third line constainsIt is guaranteed that the total number of soda in the input doesn’t exceed 1000000. The number of test cases in the input doesn’t exceed 600.
Output
For each test case, output the maximum number of soda. Then in the second line output a permutation ofdenoting the invitation order. If there are multiple solutions, print any of them.
Sample Input
484 1 3 2 2 1 0 35 3 6 4 2 1 7 683 3 2 0 5 0 3 64 5 2 7 7 6 7 682 2 3 3 3 0 0 27 4 3 6 3 2 2 585 6 5 3 3 1 2 46 7 7 6 5 4 3 5
Sample Output
71 7 6 5 2 4 3 884 6 3 1 2 5 8 773 6 7 1 5 2 8 401 2 3 4 5 6 7 8
Source
思路：用结构体存数据，x代表左区间，y代表右区间，将输入的数据按照x从小到大排序，寻找符合条件的人，找到之后压进优先队列，队列内按照y从小到大排序，这样就能保证队列的第一个数据就是当前sum所表示的人数的最佳匹配人
题目链接：点击打开链接
#include<iostream>#include<algorithm>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<queue>using namespace std;struct node{int x;int y;int z;} p[100010];int a[100010];int v[100010];int n;bool cmp(node a,node b){if(a.x == b.x){return a.y<b.y;}return a.x < b.x;}bool operator < (const node &a, const node &b){if(a.y == b.y){return a.x > b.x;}return a.y > b.y;}int main(){int T;scanf("%d",&T);while(T–){scanf("%d",&n);for(int i=0; i<n; i++){scanf("%d",&p[i].x);p[i].z = i+1;}for(int i=0; i<n; i++){scanf("%d",&p[i].y);}memset(v,0,sizeof(v));sort(p,p+n,cmp);priority_queue<node>q;while(!q.empty()){q.pop();}int sum = 0;for(int i=0; i<n; i++){if(sum >= p[i].x){q.push(p[i]);}else{i–;while(!q.empty() && (q.top().y<sum)){struct node f = q.top();q.pop();}if(q.size() == 0){break;}else{sum++;a[sum] = q.top().z;q.pop();v[a[sum]] = 1;}}}while(!q.empty()){if(sum>q.top().y){q.pop();}else{sum++;a[sum] = q.top().z;q.pop();v[a[sum]] = 1;}}printf("%d\n",sum);if(sum == 0){for(int i=1; i<=n; i++){if(i == n){printf("%d\n",i);}else{printf("%d ",i);}}}else{for(int i=1;i<=n;i++){if(v[i] == 0){printf("%d ",i);}}for(int i=1;i<=sum;i++){if(i == sum){printf("%d\n",a[i]);}else{printf("%d ",a[i]);}}}}return 0;}
版权声明：本文为博主原创文章，，如有特殊需要请与博主联系 QQ ： 793977586。
今天又是美好的一天，我要展示出我优秀的一面。不必一味讨好别人
