题目描述

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

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

输入描述：输入为空格分开的小朋友编号和是否同班标志，比如：

6/N 2/Y 3/N 4/Y

表示 4 位小朋友，2 和 6 同班，3 和 2 不同班，4 和 3 同班。小朋友总数不超过 999，每个小朋友编号大于 0，小于等于 999。不考虑输入格式错误问题。

输出描述：输出为两行，每一行记录一个班小朋友的编号，编号用空格分开，且按升序排列。若只有一个班的小朋友，第二行为空行。若输入不符合要求，直接输出 ERROR。

解题思路

1. 输入验证：检查每个编号和标志是否合法，编号应在 [1, 999] 范围内，并且第一个小朋友的标志不能为 Y。若验证不通过，输出 ERROR。
2. 分班逻辑：用两个列表 class1 和 class2 来分别存放两个班的学生编号,isClass1 和 isClass2 来分别表示上一个学生在哪一个班级。根据 Y 或 N 的标志来决定编号应加入哪个班。
   • 若标志为 Y，表示与前一位小朋友同班，加入当前班级；
   • 若标志为 N，表示与前一位小朋友不同班，切换班级。
3. 排序输出：将两个班的编号分别排序后输出，编号小的班排在第一行，编号大的班排在第二行。

复杂度分析

• 时间复杂度：O(n * log(n))，主要用于对两个班级的编号排序。
• 空间复杂度：O(n)，存储两个班级的编号。

代码实现

C++

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

// 检查编号和标志的合法性
bool check(int id, char flag, bool isFirst) {
    if (id <= 0 || id > 999) {  // 编号应在1到999范围内
        cout << "ERROR";
        return false;
    }
    if (isFirst && flag == 'Y') {  // 第一个小朋友的标志不能是Y
        cout << "ERROR";
        return false;
    }
    return true;
}

int main() {
    bool isFirst = true;  // 标记是否是第一个小朋友
    bool isClass1 = false;  // 当前班级是否为class1
    vector<int> class1, class2;  // 存放两个班的小朋友编号
    int id;  // 小朋友编号
    char flag;  // 是否同班标志
    int num = 0;  // 计数小朋友总数

    // 输入处理
    while (cin >> id) {
        getchar();
        cin >> flag;
        if (!check(id, flag, isFirst)) {  // 检查输入合法性
            return 0;
        }
        isFirst = false;
        // 根据标志Y/N决定加入哪个班级
        if ((flag == 'Y' && isClass1) || (flag == 'N' && !isClass1)) {
            isClass1 = true;
            class1.emplace_back(id);
        } else {
            isClass1 = false;
            class2.emplace_back(id);
        }
        num++;
    }
    if (num > 999) {  // 小朋友总数不应超过999
        cout << "ERROR";
        return 0;
    }

    // 对两个班级的编号进行排序
    sort(class1.begin(), class1.end());
    sort(class2.begin(), class2.end());

    // 保证编号小的班级输出在前
    if (class1.empty() || (!class2.empty() && class1[0] > class2[0])) {
        swap(class1, class2);
    }

    // 输出结果
    for (auto i : class1) cout << i << " ";
    cout << endl;
    for (auto i : class2) cout << i << " ";
    cout << endl;

    return 0;
}

Python

def check(id, flag, is_first):
    if id <= 0 or id > 999:  # 编号应在1到999范围内
        print("ERROR")
        return False
    if is_first and flag == 'Y':  # 第一个小朋友的标志不能是Y
        print("ERROR")
        return False
    return True

def main():
    is_first = True
    is_class1 = False
    class1, class2 = [], []
    num = 0
    
    # 输入处理
    try:
        inputs = input().split()
        for entry in inputs:
            id, flag = entry.split('/')
            id = int(id)
            if not check(id, flag, is_first):
                return
            is_first = False
            if (flag == 'Y' and is_class1) or (flag == 'N' and not is_class1):
                is_class1 = True
                class1.append(id)
            else:
                is_class1 = False
                class2.append(id)
            num += 1
        if num > 999:  # 小朋友总数不应超过999
            print("ERROR")
            return
    except:
        print("ERROR")
        return
    
    # 对两个班级的编号进行排序
    class1.sort()
    class2.sort()
    
    # 保证编号小的班级输出在前
    if class1 and (not class2 or class1[0] < class2[0]):
        print(" ".join(map(str, class1)))
        print(" ".join(map(str, class2)))
    else:
        print(" ".join(map(str, class2)))
        print(" ".join(map(str, class1)))

main()

Java

import java.util.*;

public class Main {
    // 检查编号和标志的合法性
    public static boolean check(int id, char flag, boolean isFirst) {
        if (id <= 0 || id > 999) {  // 编号应在1到999范围内
            System.out.println("ERROR");
            return false;
        }
        if (isFirst && flag == 'Y') {  // 第一个小朋友的标志不能是Y
            System.out.println("ERROR");
            return false;
        }
        
        return true;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        boolean isFirst = true;
        boolean isClass1 = false;
        List<Integer> class1 = new ArrayList<>();
        List<Integer> class2 = new ArrayList<>();
        int num = 0;

        try {
            while (scanner.hasNext()) {
                String[] parts = scanner.next().split("/");
                int id = Integer.parseInt(parts[0]);
                char flag = parts[1].charAt(0);

                if (!check(id, flag, isFirst)) {
                    return;
                }
                isFirst = false;

                if ((flag == 'Y' && isClass1) || (flag == 'N' && !isClass1)) {
                    isClass1 = true;
                    class1.add(id);
                } else {
                    isClass1 = false;
                    class2.add(id);
                }
                num++;
            }
            if (num > 999) {  // 小朋友总数不应超过999
                System.out.println("ERROR");
                return;
            }
        } catch (Exception e) {
            System.out.println("ERROR");
            return;
        }

        // 对两个班级的编号进行排序
        Collections.sort(class1);
        Collections.sort(class2);

        // 保证编号小的班级输出在前
        if (class1.isEmpty() || (!class2.isEmpty() && class1.get(0) > class2.get(0))) {
            List<Integer> tmp = class1;
            class1 = class2;
            class2 = tmp;
        }

        // 输出结果
        for (int i : class1) System.out.print(i + " ");
        System.out.println();
        for (int i : class2) System.out.print(i + " ");
        System.out.println();
    }
}

题目描述

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

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

输入描述

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

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

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

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

输出描述

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

编号需按照大小升序排列，分班记录中第一个编号小的排在第一行。

若只有一个班的小朋友，第二行为空行。

若输入不符合要求，则直接输出字符串 $ERROR$ 。

样例1

输入

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

输出

1 2
3 4

说明

$2$ 的同班标记为 $Y$ ，因此和 $1$ 同班。

$3$ 的同班标记为 $N$ ，因此和 $1$、$2$ 不同班。

$4$ 的同班标记为 $Y$ ，因此和 $3$ 同班。

所以 $1$ 、$2$ 同班，$3$、$4$ 同班，输出为 $1$ $2$ $3$ $4$

样例2

输入

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

输出

1 2
3 4 5