首页 > 试题广场 >

幼儿园分班

[编程题]幼儿园分班
  • 热度指数：2897 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
幼儿园一个大班要分成两个小班，有些小朋友不希望自己和其他某几位小朋友同班。园长向大家收集了不希望同班的要求，然后视情况将一个大班的小朋友分成两个班。请你开发一个程序，帮助园长快速判断是否所有小朋友的不同班请求都可以被满足。

输入描述:
输入分为三部分，第一个部分是一个 int，代表这个大班里小朋友的总数。第二部分是一个 int，代表园长采集到的小朋友们的请求数。第三部分是小朋友们的请求，每个请求由两个 int 组成，第一个 int 代表提请求的小朋友，第二个 int 代表他不希望同班的另一位小朋友。


输出描述:
如果所有小朋友的请求都可以被满足，输出 1，否则输出 0。
示例1

输入

5
5
1 2
1 3
1 4
1 5
2 3

输出

0

说明

总共有 5 位小朋友，总共采集到了 5 个请求。分别是：1 不希望和 2 同班。1 不希望和 3 同班。1 不希望和 4 同班。1 不希望和 5 同班。2 不希望和 3 同班。不能满足所有人的请求，输出 0。
示例2

输入

5
4
1 2
1 3
1 4
1 5

输出

1

说明

总共有 5 位小朋友，总共采集到了 4 个请求。分别是：1 不希望和 2 同班。1 不希望和 3 同班。1 不希望和 4 同班。1 不希望和 5 同班。可以满足所有人的请求，分班方式：1 一个人一班，2、3、4、5 另一班。输出 1。
算法知识视频讲解
添加回答
Python
月亮上的熊猫头像 月亮上的熊猫
思路：找规律后暴力。
所有的数据输入后，互斥的两个小朋友为a，b。
假设，新分的两个班为x，y。
逐个读取互斥的两个小朋友，有以下几种情况：
（1） a，b已在同一个班内，无法分班，返回0
（2）a，b都不在任何一个班内，把a加入x班，b加入y班
（3）a在x班，但b不在同一个班内，把a加入x班，b加入y班
接下来的（4）（5）（6）同理可得。
如果处理完了所有互斥请求，则分班完成，返回1 
n = int(input())
q = int(input())
a = []
b = []
for i in range(q):
    ai,bi = list(map(int,input().split()))
    a.append(ai)
    b.append(bi)
    
x = []
y = []
for i in range(q):
    if (a[i] in x and b[i] in x) or (a[i] in y and b[i] in y):
        print(0)
        exit()
    elif a[i] not in x and a[i] not in y and b[i] not in x and b[i] not in y:
        x.append(a[i])
        y.append(b[i])
    elif a[i] in x and b[i] not in x:
        x.append(a[i])
        y.append(b[i])
    elif b[i] in x and a[i] not in x:
        x.append(b[i])
        y.append(a[i])
    elif a[i] in y and b[i] not in y:
        y.append(a[i])
        x.append(b[i])
    elif b[i] in y and a[i] not in y:
        y.append(b[i])
        x.append(a[i])
print(1)
编辑于 2019-08-21 21:55:51 回复(2)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 数组 运维工程师 前端工程师 算法工程师 测试工程师 图 PHP工程师 小红书 递归 贪心 模拟 2019 Java工程师
上传者：小小
难度：
1条回答 9401浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号