Xuetangx:Data Structure and Algorithm of Tsinghua University 晋级全校公选课 PA1 THU2017spring 1-1 Team
THU2017spring 1-1 Team
描述
教练员A、B和C将要从编号为1到n的队员中挑选自己的队员。为公平起见，每个教练都根据自己的喜好程度将队员排序；你负责根据以下规则为他们分配队员。
你拿到的数据是a、b、c三个数组，表示三个教练对队员的喜好程度排序，每个数组都是数字1到n的一个排列，下标越小表示教练越喜欢该队员。你的分组规则是，从还未被分配的队员中找一个教练A最喜欢的队员分到A组；然后，在未分配的队员中分配教练B最喜欢的队员到B组；然后是教练C；再是教练A、B……依次类推直到所有队员分配完毕。
现在队员k希望知道自己被分配给哪位教练，请你来告诉他。
输入
共5行。
第1行包含一个整数n。
第2至4行依次是数组a、b和c，每行都是整数[1, n]的一个排列。
第5行包含一个整数k。
输出
仅一个字符，A、B或C，表示队员k被分配给哪位教练。
输入样例1
3
1 2 3
1 2 3
1 2 3
3
输出样例1
C
输入样例2
5
1 2 3 4 5
1 3 5 4 2
5 4 3 2 1
4
输出样例2
B
限制
1 <= n <= 500,000
1 <= k <= n
时间：1 sec
空间：256 MB
提示
● 大体上，1 sec内，O(n)的算法可以通过n = 10,000,000规模的数据，O(nlogn)通过500,000规模，O(n^2)通过5,000规模。
● 本题等一些复杂度是O(n)的题目受限于scanf(“%d”, …)的读入速度，但又不希望通过读取二进制文件等不直观的方式增加同学们的负担。
● “懒删除”策略：从序列中移除一个元素时，可以只标记它，下次读取时跳过它，而不需要将它后面的元素都向前挪一位。思考如何做标记，能在每个教练员选队员时，快速地知道该队员是否已被选走。
Tips：清零或赋值时，memset比手动赋值快几倍。输入数据时，有时scanf比cin快一些。关于读写速度，请参考Tutorial Collection #1 5.大数据(Big)。
题解：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | #include<iostream> #include<cstring> #define Rep(i,n) for(int i=0;i<n;i++) using namespace std; int main(){ ios::sync_with_stdio(false); int n,k; cin>>n; int * A=new int[n]; int * B=new int[n]; int * C=new int[n]; bool * flag=new bool[n+1]; Rep(i,n)cin>>A[i]; Rep(i,n)cin>>B[i]; Rep(i,n)cin>>C[i]; cin>>k; memset(flag,false,sizeof(bool)*(n+1)); int ptrA=0,ptrB=0,ptrC=0; for(int i=1;i<=n;i++){ if(i%3==1){ while(flag[A[ptrA]])ptrA++; flag[A[ptrA]]=true; if(A[ptrA]==k){ cout<<"A"; break; } }else if(i%3==2){ while(flag[B[ptrB]])ptrB++; flag[B[ptrB]]=true; if(B[ptrB]==k){ cout<<"B"; break; } }else if(i%3==0){ while(flag[C[ptrC]])ptrC++; flag[C[ptrC]]=true; if(C[ptrC]==k){ cout<<"C"; break; } } } return 0; } |