1842: 蓝桥杯2017年第八届真题-对局匹配(3.16)

解题思路:贪心,统计每一个积分的权值,取权值大于等于0的积分,权值=该积分的人数-(积分+k)的人数-(积分-k)的人数,因为选了该积分,那么相差k的都不能选,如果权值大于等于0说明,选该积分能提供的人数多于等于它排除的人数,可以选择
注意事项:在这个网站AC了,但在官网只对了1个,后面全是错误,没VIP看不了,求大佬指导

参考代码:

import collections


n, k = map(int, input().strip().split())
nums = list(map(int, input().strip().split()))
count = collections.Counter(nums)#统计各积分对应的人数
weight = [[float("-inf"), 0, 0, 0] for _ in range(200001)]#四个值分别对应:权值,积分,积分+k,积分-k(后三个是为了flag判断存储的下标)
flag = [True for _ in range(200001)]#标记是否能选择
if k == 0:#k=0说明只要统计有几种不同的积分即可
    print(len(set(nums)))
else:
    for each in count.keys():
        weight[each][0] = count[each] - count[each + k] - count[each - k]#计算权值
        weight[each][1] = each
        weight[each][2] = each - k
        weight[each][3] = each + k
    weight.sort(key = lambda x: x[0], reverse = True)#这里进行了降序排序,原来的下标会被打乱,无法对应原flag,所以有了上面的后三个值
    max_num = 0
    for i in range(len(weight)):
        if weight[i][0] < 0:#说明不可能被选择,因为有更好的选择
            break
        if flag[weight[i][1]]:#如果可选
            max_num += count[weight[i][1]] #加上积分对应的人数
            flag[weight[i][2]], flag[weight[i][3]] = False, False # 把相差k的给标记为False
    print(max_num)