题解 | #幼儿园分班#

幼儿园分班

https://www.nowcoder.com/practice/e503f18d56754ad9bcf8631adf63721d

解题思路

这是一道分班问题，主要思路如下：

问题分析：
- 一个大班要分成两个小班
- 每个小朋友可能不希望和某些人同班
- 需要判断是否能满足所有要求
- 本质是一个二分图染色问题
解决方案：
- 使用两个数组记录每个小朋友的分班情况
- 对于每个请求 $(a,b)$ ，尝试将 $a,b$ 分到不同班
- 如果发现冲突，则无法满足要求
- 贪心策略：遇到新的请求就立即分班
实现细节：
- 使用数组标记每个小朋友在不同班级的状态
- 0表示未分配，1表示不能在该班
- 处理每对不想同班的请求

代码

cpp
java
python

#include <iostream>
using namespace std;

int main() {
    int first[10000] = {0}, second[10000] = {0};
    int m, n;  // m为总人数，n为请求数
    
    cin >> m >> n;
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        
        // 尝试将a分到第一班，b分到第二班
        if(first[a] == 0 && second[b] == 0) {
            first[b] = 1;  // b不能进第一班
            second[a] = 1;  // a不能进第二班
        }
        // 尝试将a分到第二班，b分到第一班
        else if(first[b] == 0 && second[a] == 0) {
            first[a] = 1;
            second[b] = 1;
        }
        else {
            cout << "0" << endl;  // 无法满足要求
            return 0;
        }
    }
    
    cout << "1" << endl;  // 可以满足所有要求
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] first = new int[10000];
        int[] second = new int[10000];
        
        int m = sc.nextInt();  // 总人数
        int n = sc.nextInt();  // 请求数
        
        for(int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            
            // 尝试将a分到第一班，b分到第二班
            if(first[a] == 0 && second[b] == 0) {
                first[b] = 1;  // b不能进第一班
                second[a] = 1;  // a不能进第二班
            }
            // 尝试将a分到第二班，b分到第一班
            else if(first[b] == 0 && second[a] == 0) {
                first[a] = 1;
                second[b] = 1;
            }
            else {
                System.out.println("0");  // 无法满足要求
                return;
            }
        }
        
        System.out.println("1");  // 可以满足所有要求
        sc.close();
    }
}

def can_satisfy_requests(m: int, requests: list) -> bool:
    first = [0] * 10000
    second = [0] * 10000
    
    for a, b in requests:
        # 尝试将a分到第一班，b分到第二班
        if first[a] == 0 and second[b] == 0:
            first[b] = 1  # b不能进第一班
            second[a] = 1  # a不能进第二班
        # 尝试将a分到第二班，b分到第一班
        elif first[b] == 0 and second[a] == 0:
            first[a] = 1
            second[b] = 1
        else:
            return False
    return True

def main():
    m = int(input())
    n = int(input())
    requests = []
    for _ in range(n):
        a, b = map(int, input().split())
        requests.append((a, b))
    
    print("1" if can_satisfy_requests(m, requests) else "0")

if __name__ == "__main__":
    main()