关于算法-数据结构:PAT甲级2020年春季考试-72-The-Judger

7-2 The Judger (25 分)

A game of numbers has the following rules: at the beginning, two distinct positive integers are given by the judge. Then each player in turn must give a number to the judge. The number must be the difference of two numbers that are previously given, and must not be duplicated to any of the existed numbers. The game will run for several rounds. The one who gives a duplicate number or even a wrong number will be kicked out.

Your job is to write a judger program to judge the players’ numbers and to determine the final winners.

Input Specification:

Each input file contains one test case. For each case, the first line gives two distinct positive integers to begin with. Both numbers are in $[1,10​^5​​]$.

In the second line, two numbers are given: N (2≤N≤10), the number of players, and $M (2≤M≤10​^3​​)$, the number of rounds.

Then N lines follow, each contains M positive integers. The i-th line corresponds to the i-th player (i=1,⋯,N). The game is to start from the 1st player giving his/her 1st number, followed by everybody else giving their 1st numbers in the 1st round; then everyone give their 2nd numbers in the 2nd round, and so on so forth.

Output Specification:

If the i-th player is kicked out in the k-th round, print in a line Round #k: i is out.. The rest of the numbers given by the one who is out of the game will be ignored. If more than one player is out in the same round, print them in increasing order of their indices. When the game is over, print in the last line Winner(s): W1 W2 ... Wn, where W1 ... Wn are the indices of the winners in increasing order. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the beginning or the end of the line. If there is no winner, print No winner. instead.

Sample Input 1:

101 42
4 5
59 34 67 9 7
17 9 8 50 7
25 92 43 26 37
76 51 1 41 40

Sample Output 1:

Round #4: 1 is out.
Round #5: 3 is out.
Winner(s): 2 4

Sample Input 2:

42 101
4 5
59 34 67 9 7
17 9 18 50 49
25 92 58 1 39
102 32 2 6 41

Sample Output 2:

Round #1: 4 is out.
Round #3: 2 is out.
Round #4: 1 is out.
Round #5: 3 is out.
No winner.

题目限度：

题目粗心：

当初有 N 个玩家一起玩一个游戏，开始会先给出 2 个数字, 游戏进行 M 轮，每一轮将会从第一个玩家开始给出一个数字，直到最初一个，给出的数字如果之前有人给出过，那么阐明给的是 duplicate number 以后人被淘汰，或者给出的数字无奈在所有曾经给出的数字中找到 2 个数的差等于该数，阐明该数是 wrong number，该人被淘汰，否则以后玩家升级，同时该数字记录为曾经给出的数字，被淘汰的玩家在下一轮较量中不再参加比拟。现要求输入每一轮淘汰的玩家的编号和较量完结的时候赢家的编号，如果没有赢家输入 No winner.

算法思路：

该题题意须要好好了解，要害是这句话

The game is to start from the 1st player giving his/her 1st number,followed by everybody else giving their 1st numbers in the 1st round; then everyone give their 2nd numbers in the 2nd round,and so on so forth.

这句话给出了游戏的规定，意思是每一轮较量，从第一个选手开始给出一个数字，进行比拟是否呈现是否能够在曾经给出的数字中查找到 2 数的差值为该数，该过程完结后，才进行下一个玩家的判断，对应上例子就是定住一列，从上往下看，每次出队一个数字，而后比拟，如果没有被淘汰，该数字会增加到曾经存在的汇合中，作为下一次的比拟查找过程汇合的一部分。
明确这一点后，思路就清晰了，咱们应用 exist_numbers 存储所有以后曾经呈现过的数字，isExist 标记曾经存在的数字，应用 hasDifference(n)函数判断是否存在 exist_numbers 中的两个数字的差为 n，判断的思路就是通过假如 a,b 为 exist_numbers 中的两个数，那么判断 a -b= n 或者 b -a=n，其等价模式为 a =b+ n 或者 b =a+n, 直接判断是否存在一个数字 a 在 exist_numbers 中，a+ n 是否也在 exist_numbers 中就行了，代码如下：

// 判断是否存在 exist_numbers 中的两个数字的差为 n
bool hasDifference(int n){for(int num:exist_numbers){if(isExist[num+n]){
            // 存在
 return true;
        }
    }
    return false;
}

而后咱们应用 outPlayer 数组存储在以后轮所有被淘汰的人，out 标记每一个淘汰的玩家，遍历每一个没有被淘汰的玩家，应用 isOut 标记以后玩家是否淘汰，其规定就是 isOut = isExist[number[i][j]]||!hasDifference(number[i][j])(number[i][j] 示意第 i 个 player 在第 j 轮出的数字)，只有 isOut 为 true，阐明该玩家被淘汰，将其退出到 outPlayer 中，并将以后人的淘汰标记设置为 true(out[i] = true), 否则该玩家升级，将其数字增加到exist_numbers 汇合中，并标记该数字以及存在。在以后轮次比拟结束后，就输入所有的被淘汰的玩家。如果较量完结，就遍历 out 数组，将所有没有被淘汰的玩家增加到 winners 汇合中，最初如果 winners 不为空，输入每一个玩家，否则输入No winner.

留神点：

• 1、exist_numbers应用 vector 有可能会导致测试点 5 运行超时，应用 unordered_set 和set就能够，然而应用 vector 多提交几次也能够通过
• 2、测试点 2 和 5 考查多人淘汰的状况，也就是有多人淘汰的时候，是每次输入一行 Round #k: i is out. 而不是将所有人集中在一起输入，比方 Round #k: i j is out. 就是谬误的
• 3、以后玩家如果被淘汰，其对应的数字不能增加到 exist_numbers，也就是算在曾经呈现的数字汇合中，换句话说，在曾经呈现的数字汇合中，肯定是任意 2 数的差值还在该汇合中，测试点 6 考查。

提交后果：

AC 代码：

#include<cstdio>
#include<vector>
#include<unordered_map>
#include<unordered_set>

using namespace std;

int number[15][1005];// number[i][j]示意第 i 个 player 在第 j 轮出的数字
unordered_set<int> exist_numbers;// 所有以后曾经呈现过的非法数字, 应用 vector 有可能会超时，然而会呈现通过的状况
unordered_map<int,bool> isExist;// 标记曾经存在的数字
bool out[20];// 标记每一个淘汰的玩家

// 判断是否存在 exist_numbers 中的两个数字的差为 n
bool hasDifference(int n){for(int num:exist_numbers){if(isExist[num+n]){
            // 存在
            return true;
        }
    }
    return false;
}

int main(){
    int a,b;
    scanf("%d %d",&a,&b);
    exist_numbers.insert(a);
    exist_numbers.insert(b);
    isExist[a] = isExist[b] = true;
    int N,M;// 玩家数目和轮次
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;++i){for(int j=1;j<=M;++j){scanf("%d",&number[i][j]);
        }
    }
    // 开始较量
    for(int j=1;j<=M;++j){// 每一轮
        vector<int> outPlayer;// 在以后轮所有被淘汰的人
        for(int i=1;i<=N;++i){// 每一个玩家
            if(!out[i]){bool isOut = isExist[number[i][j]]||!hasDifference(number[i][j]);// 曾经存在过了或者没有差值存在为 true
                if(isOut){
                    // 将对应的玩家增加到淘汰队列中
                    outPlayer.push_back(i);
                    out[i] = true;
                } else{// 测试点 6 考查，只有在以后用户没有被淘汰的时候就将该人的数字增加到汇合中
                    // 将以后数字退出到 exist_numbers 中，exist_numbers.insert(number[i][j]);
                    isExist[number[i][j]] = true;
                }
            }
        }
        // 以后轮次比拟结束
        for(int item:outPlayer){
            // 输入被淘汰的人，如果没有就不会输入
            printf("Round #%d: %d is out.\n",j,item);
        }
    }
    // 遍历所有的人，判断是否还有赢家
    vector<int> winners;
    for(int i=1;i<=N;++i){if(!out[i]){winners.push_back(i);
        }
    }
    if(!winners.empty()){printf("Winner(s):");
        for(int winner:winners){printf("%d",winner);
        }
    }else{printf("No winner.");
    }
    return 0;
}