刷题笔记合集🔗

分班

问题描述

幼儿园两个班的小朋友在排队时混在了一起，每位小朋友都知道自己是否与前面一位小朋友同班，请你帮忙把同班的小朋友找出来。

小朋友的编号是整数，与前一位小朋友同班用Y表示，不同班用N表示。

输入格式

输入为空格分开的小朋友编号和是否同班标志。

比如：6/N 2/Y 3/N 4/Y，表示4位小朋友，2和6同班，3和2不同班，4和3同班。

其中，小朋友总数不超过999，每个小朋友编号大于0，小于等于999。

不考虑输入格式错误问题。

输出格式

输出为两行，每一行记录一个班小朋友的编号，编号用空格分开，且：

1. 编号需按照大小升序排列，分班记录中第一个编号小的排在第一行。
2. 若只有一个班的小朋友，第二行为空行。
3. 若输入不符合要求，则直接输出字符串ERROR。

样例输入

1/N 2/Y 3/N 4/Y

1/N 2/Y 3/N 4/Y 5/Y

样例输出

1 2
3 4

1 2
3 4 5

数据范围

• 小朋友总数不超过999
• 每个小朋友编号大于0，小于等于999

题解

这道题目要求我们将混合在一起的两个班级的小朋友重新分班。题目给出了每个小朋友是否与前一位小朋友同班的信息，我们需要据此还原出每个班级包含哪些小朋友。

解题的关键在于理解题目中的标记含义：

• N表示当前小朋友与前一位小朋友不同班
• Y表示当前小朋友与前一位小朋友同班

首先需要处理一些边界情况和错误检查：

1. 第一个小朋友前面没有人，所以其标记必须是N，如果是Y则为错误
2. 检查小朋友的编号是否在合法范围内：大于0且小于等于999
3. 检查小朋友总数是否不超过999

解题思路如下：

1. 定义两个列表分别存储一班和二班的小朋友编号
2. 设置一个标志preBelongToOne表示前一个小朋友是否属于一班
3. 遍历每个小朋友，根据其是否与前一位同班的标记来决定其班级：
   • 如果前一个小朋友属于一班：
     • 若当前小朋友与前一个同班(Y)，则当前小朋友也属于一班
     • 若当前小朋友与前一个不同班(N)，则当前小朋友属于二班
   • 如果前一个小朋友属于二班：
     • 若当前小朋友与前一个同班(Y)，则当前小朋友也属于二班
     • 若当前小朋友与前一个不同班(N)，则当前小朋友属于一班
4. 最后，对两个班级的小朋友编号进行排序，并按要求输出

这种解法的时间复杂度是O(n log n)，其中n是小朋友的数量，主要消耗在排序操作上。空间复杂度是O(n)，用于存储两个班级的小朋友编号。

这个问题本质上是一个图论中的二分图问题，我们通过遍历给定的关系，将小朋友分到两个不相交的集合中。算法相对简单直观，没有使用复杂的数据结构，适合快速实现。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

def solve(input_str):
    # 解析输入
    kids = [item.split('/') for item in input_str.split()]
    
    # 检查小朋友总数是否不超过999
    if len(kids) > 999:
        return "ERROR"
    
    # 第一个小朋友前面没有人，标记必须是N
    if kids[0][1] == "Y":
        return "ERROR"
    
    # 存储两个班级的小朋友编号
    class1 = []
    class2 = []
    
    # 前一个小朋友是否属于一班，初始为假
    pre_in_class1 = False
    
    for kid in kids:
        # 解析小朋友编号
        kid_id = int(kid[0])
        
        # 检查小朋友编号是否在合法范围内
        if kid_id <= 0 or kid_id > 999:
            return "ERROR"
        
        # 判断当前小朋友是否与前一位同班
        is_same_with_pre = kid[1] == "Y"
        
        # 根据前一个小朋友所在班级和是否同班决定当前小朋友班级
        if pre_in_class1:
            if is_same_with_pre:
                class1.append(kid_id)
            else:
                class2.append(kid_id)
                pre_in_class1 = False
        else:
            if is_same_with_pre:
                class2.append(kid_id)
            else:
                class1.append(kid_id)
                pre_in_class1 = True
    
    # 对两个班级的小朋友编号排序
    class1.sort()
    class2.sort()
    
    # 若只有一个班的小朋友，第二行为空行
    if not class2:
        return f"{' '.join(map(str, class1))}\n"
    
    # 分班记录中第一个编号小的排在第一行
    if class1[0] < class2[0]:
        return f"{' '.join(map(str, class1))}\n{' '.join(map(str, class2))}"
    else:
        return f"{' '.join(map(str, class2))}\n{' '.join(map(str, class1))}"

# 读取输入并输出结果
print(solve(input()))

• Cpp

#include <bits/stdc++.h>
using namespace std;

string solve(const string& input_str) {
    // 解析输入
    istringstream iss(input_str);
    vector<pair<int, string>> kids;
    string item;
    
    while (iss >> item) {
        size_t pos = item.find('/');
        int id = stoi(item.substr(0, pos));
        string mark = item.substr(pos+1);
        kids.push_back({id, mark});
    }
    
    // 检查小朋友总数是否不超过999
    if (kids.size() > 999) {
        return "ERROR";
    }
    
    // 第一个小朋友前面没有人，标记必须是N
    if (kids[0].second == "Y") {
        return "ERROR";
    }
    
    // 存储两个班级的小朋友编号
    vector<int> class1,