PAT(甲级)2020年春季考试 7-2 The Judger (25 分) 经验分享与心路历程

做了1个小时,过样例

#include <bits/stdc++.h>
using namespace std;


unordered_map<int, bool> exist;
unordered_map<int, bool>  difference;
vector<vector<int>> input;
//玩家的下标是直接从1到n开始的
unordered_map<int, bool> out_game;

int main()
{
#ifndef ONLINE_JUDGE
    FILE* s;
    freopen_s(&s, "in.txt", "r", stdin);
#endif // !ONLINE_JUDGE
    //我们现在首先需要把这个数据做一个拆分
    //做差比较的过程需要加入,
    //一个是做差的表,一个是已经加入数值的表
    //一个数需要和这些表进行比较,必须要存在,如果不存在的话就直接判断错误
    int n1, n2;
    cin >> n1 >> n2;
    //这两个数就要先做差然后加入做差的表
    //做差的时候必须被减数较大,不能小于这些的数值,最后的结果不能是负的
    //每轮的数据我们用嵌套的向量来保存用户的输入信息
    exist[n1] = true;
    exist[n2] = true;
    if (n1 > n2) {
        difference[n1 - n2] = true;
        //exist[n1 - n2] = true;
    }
    else {
        difference[n2 - n1] = true;
        //exist[n2 - n1] = true;
    }
    //之后我们把整组的这个数据给加入的向量里面
    int n, m;
    cin >> n >> m;
    //大小设置成n+1
    input.resize(n + 1);
    int t;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> t;
            input[i].push_back(t);
        }
    }
    //在录入完用户数据以后需要按照一轮轮的进行处理,我们数据录入以后首先是要考虑会不会和已有的数据重复了
    //在一轮轮的时候我们需要遍历每个玩家给出的数据,判断的标准就是
    //轮次在遍历的时候是固定的,我们需要有一个数组来淘汰
    //相关的内容,如果说玩家出局了,我们把向量清空来进行标记
    //或者开一个out的数组,在查询之前首先进行检查
    //一般来说不要把相关的原始数据清空,作为一个
    //我们在读到这个相关的数据的时候,我们在做差完也需要把相关的数据加入存在数组
    //存在数组里面有那么多的数据,
    for (int i = 0; i < m; i++) {
        vector<int> out;
        //一轮里面可能需要淘汰多个的数据,在多轮结束以后,如果未被标记的话就认为是胜出的玩家
        for (int j = 1; j <= n; j++) {//j代表的是玩家的下标
            if (out_game[j] != true) {
                if (exist[input[j][i]] != true) {
                    //如果元素已经存在的话,需要考虑其是否已经在系统之前探索的做差的范围里面
                    if (difference[input[j][i]] == true) {
                        //在做差的范围里面的话,需要把它已经存在,我们以后尽量用true来表示存在关系
                        //我们首先需要把这个元素和已经存在的那些元素进行做差,再把做差之后的结果加入
                        //到做差的集合里面,然后把这个元素标记到存在数组里面
                        for (auto it = exist.begin(); it != exist.end(); it++) {
                            if (it->first > input[j][i]) {
                                difference[it->first - input[j][i]] = true;
                            }
                            else {
                                difference[input[j][i] - it->first] = true;
                            }
                        }
                        exist[input[j][i]] = true;
                    }
                    else {
                        //如果不在做差的范围里面
                        out_game[j] = true;
                        out.push_back(j);
                    }
                }
                else {
                    //如果一个值已经存在,我们需要把这个用户标记为出局
                    out_game[j] = true;//j代表的是玩家的下标
                    out.push_back(j);
                }
            }
        }
        if (out.size() == 1) {
            printf("Round #%d: %d is out.\n",i+1,out[0]);
        }
        else if (out.size() > 1) {
            sort(out.begin(),out.end());
            cout << out[0];
            for (int i = 1; i < out.size(); i++) {
                cout << " " << out[i];
            }
            cout << endl;
        }
    }
    //在几轮做完以后,判断相关的数组
    vector<int> winner;
    for (int i = 1; i <= n; i++) {
        if (out_game[i] != true) {
            winner.push_back(i);
        }
    }
    if(winner.size()!=0){
        sort(winner.begin(), winner.end());
        cout << "Winner(s):";
        for (int i = 0; i < winner.size(); i++) {
            cout << " " << winner[i];
        }
        cout << endl;
    }
    else {
        cout << "No winner.";
    }

    return 0;
}

 

上一篇:Java路线学习与日语n2准备的粗略计划表


下一篇:程序员数学基础【二、时间复杂度】