THU2017spring 1-1 Team 题解

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

1
2
3
4
5
3
1 2 3
1 2 3
1 2 3
3

输出样例1

1
C

输入样例2

1
2
3
4
5
5
1 2 3 4 5
1 3 5 4 2
5 4 3 2 1
4

输出样例2

1
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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注