【PAT_Python解】1115 裁判机

原题链接：PTA | 程序设计类实验辅助教学平台

Tips：以下Python代码仅个人理解，非最优算法，仅供参考！多学习其他大佬的AC代码！

测试点5：passd 有9994个不同的有效数值

测试点6：is_given 有157386个不同的差值

AC代码：

import sys

def is_pass(num, is_given, passed_numbers, passed_end):
    # 如果 num 已经被拿过，直接返回 False
    if is_given[num]:
        return False
    # 遍历已经通过的数字，检查是否满足条件
    for i in range(passed_end):
        if num < passed_numbers[i] and is_given[passed_numbers[i] - num]:
            return True
        elif num > passed_numbers[i] and is_given[passed_numbers[i] + num]:
            return True
    return False

def main():
    # 给的数值肯定就直接1w和16w，或者20w，这里是为了看看到底有多少
    passed_numbers = [0] * 9994     # 有效数值数量
    is_given = [False] * 157386     # 不同差值数量

    # 读取输入
    passed_numbers[0], passed_numbers[1] = map(int, sys.stdin.readline().split())
    N, M = map(int, sys.stdin.readline().split())

    # 将初始数字标记为已经通过
    is_given[passed_numbers[0]] = True
    is_given[passed_numbers[1]] = True

    # 创建玩家列表
    players = []
    for _ in range(N):
        numbers = list(map(int, sys.stdin.readline().split()))
        players.append({'numbers': numbers, 'isOut': False})

    passed_end = 2  # 已通过的数字个数

    # 游戏过程
    for round_index in range(M):
        for player_index in range(N):
            if players[player_index]['isOut']:
                continue
            current_number = players[player_index]['numbers'][round_index]
            # 检查是否能够通过
            if is_pass(current_number, is_given, passed_numbers, passed_end):
                # 标记当前数字为已通过
                is_given[current_number] = True
                passed_numbers[passed_end] = current_number
                passed_end += 1
            else:
                # 玩家被淘汰
                players[player_index]['isOut'] = True
                sys.stdout.write(f"Round #{round_index + 1}: {player_index + 1} is out.\n")

    # 检查赢家
    winners = [i + 1 for i in range(N) if not players[i]['isOut']]
    if winners:
        sys.stdout.write(f"Winner(s): {' '.join(map(str, winners))}")
    else:
        sys.stdout.write("No winner.")

if __name__ == "__main__":
    main()

仅测试点5超时代码：

import sys

def update_res(valid_nums, sub_res, new_num):
    # 增量更新过测试点6，只为新添加的 num 计算绝对差
    for num in valid_nums:
        sub = abs(new_num - num)
        if sub not in sub_res:
            sub_res.add(sub)

def main():
    init1, init2 = map(int, sys.stdin.readline().split())
    valid_nums = {init1, init2}
    sub_res = set()
    update_res(valid_nums, sub_res, init1)
    update_res(valid_nums, sub_res, init2)

    n, m = map(int, sys.stdin.readline().split())
    ans = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    
    winners = set(range(1, n + 1))
    for round in range(m):
        for man in range(n):
            num = ans[man][round]
            if not winners:
                sys.stdout.write('No winner.')
                return
            if man + 1 in winners:
                if num not in valid_nums and num in sub_res:
                    valid_nums.add(num)
                    update_res(valid_nums, sub_res, num)  # 增量更新
                else:
                    winners.remove(man + 1)
                    sys.stdout.write(f'Round #{round + 1}: {man + 1} is out.\n')
    
    if winners:
        res = ' '.join(map(str, winners))
        sys.stdout.write(f'Winner(s): {res}')
    else:
        sys.stdout.write('No winner.')

if __name__ == "__main__":
    main()