一道算法题n个小朋友在老师的带领下玩游戏.其中需要分组,老师打算根据大家的衣服颜色分组.已知衣服颜色用0-9的数字表示.老师决定每k个人分为一组.每一组的小朋友必须身穿同一种颜色的

Question

一道算法题
n个小朋友在老师的带领下玩游戏.
其中需要分组,老师打算根据大家的衣服颜色分组.
已知衣服颜色用0-9的数字表示.
老师决定每k个人分为一组.每一组的小朋友必须身穿同一种颜色的衣服.
请你告诉老师,是否能成功分组.
Input
仅一组数据
第一行两个整数n,k (1

Answer 1

import sys

def main():
    n, k = map(int, input().split())
    l = map(int, input().split())
    
    if n != len(l):
        print "Invalid testcase"
        sys.exit(1)
    if n % k != 0:
        print "NO"
        sys.exit(0)
    
    l.sort()
    
    while l:
        t = l[:k]
        c = map(lambda x: x == t[0], t)
        if not all(c):
            print "NO"
            sys.exit(0)
        l = [k:]
    
    print "YES"
    
main()

简单说一下这个解,

想要YES, 那么必须满足几个条件:

1, n个人可以被平均分成x组, 每组k人.

检测这个条件就求模, n % k, 就可以了

2, 每组的学生颜色相同

检测这个条件, 我们先把数列排序,

就相当于不管行不行, 我们先把组分了,

同色的人在一起.

然后就每次取k个人, 检测是否所有的人穿同样颜色的衣服, 就可以了.

while l, 当还有学生剩下

t = l[:k], 取k个学生

c = map(lambda x: x == t[0], t), 拿所有学生跟第一个学生比较

if not all(c), 如果不全都一样

那就NO

如果全都一样, 那就接着对l[k:], 也就是剩下的学生做相同的比较

因为前面检测过了n % k, 所以可以确定每次都能取到k个学生.

所有检测全都通过的话, 那么就是YES了