PAT Basic 1115. 裁判机
1. 题目描述：
有一种数字游戏的规则如下：首先由裁判给定两个不同的正整数，然后参加游戏的几个人轮流给出正整数。要求给出的数字必须是前面已经出现的某两个正整数之差，且不能等于之前的任何一个数。游戏一直持续若干轮，中间有写重复或写错的人就出局。
本题要求你实现这个游戏的裁判机，自动判断每位游戏者给出的数字是否合法，以及最后的赢家。
2. 输入格式：
输入在第一行中给出 2 个初始的正整数，保证都在 \([1,10^5]\) 范围内且不相同。
第二行依次给出参加比赛的人数 \(N\)（\(2≤N≤10\)）和每个人都要经历的轮次数 \(M\)（\(2≤M≤10^3\)）。
以下 \(N\) 行，每行给出 \(M\) 个正整数。第 \(i\) 行对应第 \(i\) 个人给出的数字（\(i=1,⋯,N\)）。游戏顺序是从第 1 个人给出第 1 个数字开始，每人顺次在第 1 轮给出自己的第 1 个数字；然后每人顺次在第 2 轮给出自己的第 2 个数字，以此类推。
3. 输出格式：
如果在第 k 轮，第 i 个人出局，就在一行中输出 Round #k: i is out.。出局人后面给出的数字不算；同一轮出局的人按编号增序输出。直到最后一轮结束，在一行中输出 Winner(s): W1 W2 ... Wn，其中 W1 ... Wn 是最后的赢家编号，按增序输出。数字间以 1 个空格分隔，行末不得有多余空格。如果没有赢家，则输出 No winner.。
4. 输入样例：
101 42
4 5
59 34 67 9 7
17 9 8 50 7
25 92 43 26 37
76 51 1 41 40
42 101
4 5
59 34 67 9 7
17 9 18 50 49
25 92 58 1 39
102 32 2 6 41
5. 输出样例：
Round #4: 1 is out.
Round #5: 3 is out.
Winner(s): 2 4
Round #1: 4 is out.
Round #3: 2 is out.
Round #4: 1 is out.
Round #5: 3 is out.
No winner.
6. 性能要求：
Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB
思路：
这道题卡了一下午。。。题目关键在于对给出数字的逻辑判断，一开始想着定义int型数组record记录出现过的数字，因为裁判给出的正整数范围属于 \([1,10^5]\) ，合法数字是已出现的两个正整数之差，并且保证玩家给出的是正整数，所以合法的正整数一定小于 \(10^5\) ，我就将record大小定义为了10^5+1（现在想想根本没有逻辑，玩家完全有可能给出非法数字，很容易造成数组越界）。然后定义子函数isDelta()判断给出的数字是否是已出现的两个正整数之差，采用之前PAT Basic 1096. 大美数 的思路，相当于遍历所有组合情况进行判断。另外定义int型数组out记录玩家出局情况并进行输出即可。第一次提交时testpoint5，testpoint6报Time Limit Exceeded，对代码进行优化，考虑到isDelta()遍历的次数过多，就换了一种记录方式，改为直接将每个出现过的数字进行存储，定义recordCount记录出现的数字个数，这样遍历时只用遍历recordCount次，修改后testpoint5仍然time limit exceeded，testpoint6报wrong answer，仔细排查后发现题意理解有问题。。。这里如果玩家 \(i\) 在当前轮次出局，那么其当前轮次给出的数字是不算的（一开始读题我以为是从下一轮此才开始不算），修改后testpoint6通过，testpoint5仍然time limit exceeded。
无奈上网搜索题解，找到一个很简洁的：2020年春季PAT乙级题解（C语言）_1115 裁判机_Spiderman_94的博客-CSDN博客 ，再次感觉到智商被压制。。。对比后发现这里超时的主要原因还是isDelta()中嵌套for循环，当循环次数比较大时是指数增长的，而这个题解都是用的一次for循环进行判断，其思路有点逆向思维：既然我要判断是否有正整数 \(a,b\) 满足 \(a-b = tempNum\)，那么只需要判断是否有 \(a = b+ tempNum\)，而我一直想着遍历两个元素减出tempNum。。。这个题解相当于将两种记录方式结合，用额外的空间换时间。
My Code:
// #include <stdio.h>
// #include <stdlib.h> // malloc header, calloc header
// #define MAX_VAL (100000+1)
// int isDelta(const int *record, int tempNum, int upBound);
// // first submit testpoint5, 6 Time Limit Exceeded
// int main(void)
// {
// int record[MAX_VAL] = {0};
// int init1=0, init2=0;
// int playerCount=0, roundCount=0;
// int i=0, j=0, k=0; // iterator
// int alivePlayer=0;
// int upBound=0;
// scanf("%d%d", &init1, &init2);
// scanf("%d%d", &playerCount, &roundCount);
// record[init1] = 1; // record judge's number
// record[init2] = 1;
// upBound = init1>init2 ? init1 : init2; // calculate upBound
// alivePlayer = playerCount; // have winner flag
// int (*pMat)[roundCount] = (int (*) [roundCount])malloc(sizeof(int) * playerCount * roundCount);
// int *out = (int *)calloc(playerCount, sizeof(int)); // record every player's state, calloc make the init value is 0
// int *printFlag = (int *)calloc(playerCount, sizeof(int));
// for(i=0; i<playerCount; ++i) // player input
// {
// for(j=0; j<roundCount; ++j)
// {
// scanf("%d", &pMat[i][j]);
// //printf("%d ", pMat[i][j]); // test input
// }
// //printf("\n");
// }
// for(j=0; j<roundCount; ++j)
// {
// for(i=0; i<playerCount; ++i)
// {
// if(!out[i]) // this player doesn't out
// {
// //if(pMat[i][j] > init1 && pMat[i][j] > init2)
// if((pMat[i][j] > init1 && pMat[i][j] > init2) || record[pMat[i][j]] || !isDelta(record, pMat[i][j], upBound))
// {
// out[i] = 1; // player i out
// --alivePlayer;
// }
// if(pMat[i][j] < init1 || pMat[i][j] < init2)
// record[pMat[i][j]] = 1; // record this player number
// }
// }
// for(k=0; k<playerCount; ++k) // print this round info
// {
// if(out[k] && !printFlag[k])
// {
// printf("Round #%d: %d is out.\n", j+1, k+1);
// printFlag[k] = 1;
// }
// }
// if(!alivePlayer) break; // no alivePlayer, exit directly
// }
// if(alivePlayer) // have alive player
// {
// printf("Winner(s):");
// for(i=0; i<playerCount; ++i) // print winner info
// {
// if(!out[i]) printf(" %d", i+1);
// }
// printf("\n");
// }
// else
// {
// printf("No winner.\n");
// }
// free(pMat);
// free(out);
// free(printFlag);
// return 0;
// }
// int isDelta(const int *record, int tempNum, int upBound) // return 1 if tempNum is a delta of two number in the record
// {
// int i=0, j=0; // iterator
// for(i=upBound; i>=1; --i)//for(i=MAX_VAL-1; i>=1; --i)
// {
// if(!record[i]) continue; // record[i] == 0, no this number
// for(j=i-1; j>=0; --j)
// {
// if(!record[j]) continue; // record[j] == 0, no this number
// //if((record[i] - record[j]) == tempNum) return 1;
// if((i - j) == tempNum) return 1;
// }
// }
// return 0;
// }
// #include <stdio.h>
// #include <stdlib.h> // malloc header, calloc header, qsort header
// #define MAX_LEN (10*1000+2) // MAX_PLAYER * MAX_ROUND + INIT1+ INIT2
// int alreadyIn(const int *record, int recordCount, int tempNum);
// int isDelta(int *record, int recordCount, int tempNum);
// int myCmp(const void *p1, const void *p2);
// // first submit testpoint5, 6 Time Limit Exceeded
// // after rectify, testpoint5 still time limit exceeded, testpoint6 wrong answer
// int main(void)
// {
// //int record[MAX_VAL] = {0};
// int init1=0, init2=0;
// int playerCount=0, roundCount=0;
// int i=0, j=0, k=0; // iterator
// int alivePlayer=0;
// //int upBound=0;
// int record[MAX_LEN] = {0};
// int recordCount=0; // count of given number
// scanf("%d%d", &init1, &init2);
// scanf("%d%d", &playerCount, &roundCount);
// // record[init1] = 1; // record judge's number
// // record[init2] = 1;
// recordCount = 0;
// record[recordCount++] = init1;
// record[recordCount++] = init2;
// alivePlayer = playerCount; // have winner flag
// int (*pMat)[roundCount] = (int (*) [roundCount])malloc(sizeof(int) * playerCount * roundCount);
// int *out = (int *)calloc(playerCount, sizeof(int)); // record every player's state, calloc make the init value is 0
// int *printFlag = (int *)calloc(playerCount, sizeof(int));
// for(i=0; i<playerCount; ++i) // player input
// {
// for(j=0; j<roundCount; ++j)
// {
// scanf("%d", &pMat[i][j]);
// //printf("%d ", pMat[i][j]); // test input
// }
// //printf("\n");
// }
// for(j=0; j<roundCount; ++j)
// {
// for(i=0; i<playerCount; ++i)
// {
// if(!out[i]) // this player doesn't out
// {
// //if(pMat[i][j] > init1 && pMat[i][j] > init2)
// //if((pMat[i][j] > init1 && pMat[i][j] > init2) || alreadyIn(record, recordCount, pMat[i][j]) || !isDelta(record, recordCount, pMat[i][j]))
// if(alreadyIn(record, recordCount, pMat[i][j]) || !isDelta(record, recordCount, pMat[i][j]))
// {
// out[i] = 1; // player i out
// --alivePlayer;
// }
// // if(pMat[i][j] < init1 || pMat[i][j] < init2)
// // record[pMat[i][j]] = 1; // record this player number
// if(!out[i]) // this fixed testpoint6, if player i out, this round number won't be add to record...
// record[recordCount++] = pMat[i][j]; // record this player number
// }
// }
// for(k=0; k<playerCount; ++k) // print this round info
// {
// if(out[k] && !printFlag[k])
// {
// printf("Round #%d: %d is out.\n", j+1, k+1);
// printFlag[k] = 1;
// }
// }
// if(!alivePlayer) break; // no alivePlayer, exit directly
// }
// if(alivePlayer) // have alive player
// {
// printf("Winner(s):");
// for(i=0; i<playerCount; ++i) // print winner info
// {
// if(!out[i]) printf(" %d", i+1);
// }
// printf("\n");
// }
// else
// {
// printf("No winner.\n");
// }
// free(pMat);
// free(out);
// free(printFlag);
// return 0;
// }
// int alreadyIn(const int *record, int recordCount, int tempNum)
// {
// int i=0; // iterator
// for(i=0; i<recordCount; ++i)
// {
// if(record[i] == tempNum) return 1; // already have tempNum
// }
// return 0;
// }
// int isDelta(int *record, int recordCount, int tempNum) // return 1 if tempNum is a delta of two number in the record
// {
// int i=0, j=0; // iterator
// int tempDelta = 0;
// qsort(record, recordCount, sizeof(int), myCmp); // sort record in ascending order
// if(record[recordCount-1] - record[0] < tempNum) return 0;
// // for(i=recordCount-1; i>=1; --i)
// // {
// // for(j=0; j<=i; ++j)//for(j=i; j>=0; --j)
// // {
// // tempDelta = record[i] - record[j];
// // //tempDelta = tempDelta>0 ? tempDelta : -tempDelta;
// // if(tempDelta == tempNum) return 1;
// // }
// // }
// for(i=0; i<= recordCount-2; ++i)
// {
// for(j=i+1; j<recordCount; ++j)
// {
// if(record[j] - record[i] == tempNum) return 1;
// }
// }
// return 0;
// }
// int myCmp(const void *p1, const void *p2)
// {
// return (*(int *)p1 - *(int *)p2);
// }
// refer to https://blog.csdn.net/qq_52491362/article/details/122844030
#include <stdio.h>
#include <stdlib.h> // malloc header, calloc header
#define MAX_LEN (10*1000+2) // MAX_PLAYER * MAX_ROUND + INIT1+ INIT2
#define MAX_VAL 200000 //(100000+1) too small will cause segmentation error
int alreadyIn(const int *record, int recordCount, int tempNum);
int isDelta(const int *record, int recordCount, const int *inFlag, int tempNum);
// first submit testpoint5, 6 Time Limit Exceeded
// after rectify, testpoint5 still time limit exceeded, testpoint6 wrong answer
int main(void)
{
int init1=0, init2=0;
int playerCount=0, roundCount=0;
int i=0, j=0, k=0; // iterator
int alivePlayer=0;
int record[MAX_LEN] = {0};
int recordCount=0; // count of given number
int inFlag[MAX_VAL] = {0};
scanf("%d%d", &init1, &init2);
scanf("%d%d", &playerCount, &roundCount);
inFlag[init1] = 1; // flag judge's number
inFlag[init2] = 1;
recordCount = 0;
record[recordCount++] = init1;
record[recordCount++] = init2;
alivePlayer = playerCount; // have winner flag
int (*pMat)[roundCount] = (int (*) [roundCount])malloc(sizeof(int) * playerCount * roundCount);
int *out = (int *)calloc(playerCount, sizeof(int)); // record every player's state, calloc make the init value is 0
int *printFlag = (int *)calloc(playerCount, sizeof(int));
for(i=0; i<playerCount; ++i) // player input
{
for(j=0; j<roundCount; ++j)
{
scanf("%d", &pMat[i][j]);
//printf("%d ", pMat[i][j]); // test input
}
//printf("\n");
}
for(j=0; j<roundCount; ++j)
{
for(i=0; i<playerCount; ++i)
{
if(!out[i]) // this player doesn't out
{
//if(pMat[i][j] > init1 && pMat[i][j] > init2)
//if((pMat[i][j] > init1 && pMat[i][j] > init2) || alreadyIn(record, recordCount, pMat[i][j]) || !isDelta(record, recordCount, pMat[i][j]))
if(alreadyIn(record, recordCount, pMat[i][j]) || !isDelta(record, recordCount, inFlag, pMat[i][j]))
{
out[i] = 1; // player i out
--alivePlayer;
}
if(!out[i]) // this fixed testpoint6, if player i out, this round number won't be add to record...
{
record[recordCount++] = pMat[i][j]; // record this player number
inFlag[pMat[i][j]] = 1; // flag pMat[i][j]
}
}
}
for(k=0; k<playerCount; ++k) // print this round info
{
if(out[k] && !printFlag[k])
{
printf("Round #%d: %d is out.\n", j+1, k+1);
printFlag[k] = 1;
}
}
if(!alivePlayer) break; // no alivePlayer, exit directly
}
if(alivePlayer) // have alive player
{
printf("Winner(s):");
for(i=0; i<playerCount; ++i) // print winner info
{
if(!out[i]) printf(" %d", i+1);
}
printf("\n");
}
else
{
printf("No winner.\n");
}
free(pMat);
free(out);
free(printFlag);
return 0;
}
int alreadyIn(const int *record, int recordCount, int tempNum)
{
int i=0; // iterator
for(i=0; i<recordCount; ++i)
{
if(record[i] == tempNum) return 1; // already have tempNum
}
return 0;
}
int isDelta(const int *record, int recordCount, const int *inFlag, int tempNum) // return 1 if tempNum is a delta of two number in the record
{
int i=0; // iterator
for(i=0; i<recordCount; ++i)
{
if(inFlag[record[i]+tempNum]) return 1; // this fixed testpoint5
}
return 0;
}
\(\infty\). 写在最后：
截至2023/4/20，PAT Basic Level题库的115道题已经刷完了，全部采用C语言，主要对于C的基础IO和一些库函数进行了熟悉，另外还有一些简单算法，如：
- 素数的判断
- 两数最大公约数的求解
也对“人生苦短，我用Python”有了切身体会，C语言过于底层了，其优势在于灵活的指针，直接操作内存，劣势也在于灵活的指针，一不小心就容易数组越界（不过还是因为我的水平有限QAQ）。还是不如C++，Python这些语言“高级”（真不会造轮子了，还是先把车开起来再说吧）。
后续应该会继续更新PAT Advanced Level，相信我，那时我将带着C++回来 orz。