dp[i]只跟dp[i-1]以及YN_lst[i]有关系。若
- 第i个小朋友和第i-1个小朋友同班，即YN_lst[i] == "Y"，那么dp[i] = dp[i-1]
- 第i个小朋友和第i-1个小朋友不同班，即YN_lst[i] == "N"，那么dp[i] = not dp[i-1]

if YN_lst[i] == "Y":
    dp[i] = dp[i-1]
elif YN_lst[i] == "N":
    dp[i] = not dp[i-1]

dp数组如何初始化？

默认第0个小朋友是在1班，故dp[0] = True

做完dp过程之后，还需要依据题目要求，对两个班的小朋友进行排序和输出。其过程如下

class1, class2 = list(), list()
for i in range(n):
    class1.append(children_lst[i]) if dp[i] else class2.append(children_lst[i])

class1.sort()
class2.sort()
if len(class2) == 0:
    print(" ".join(map(str, class1)))
    print("")
else:
    if class1[0] > class2[0]:
        class1, class2 = class2, class1
    print(" ".join(map(str, class1)))
    print(" ".join(map(str, class2)))

代码

Python

# 题目：2024E-分班
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：DP
# 代码看不懂的地方，请直接在群上提问


children_lst = list()
YN_lst = list()


# 输入原始字符串数据
s = input()
# 对s以空格作为分割符的分割子字符串sub_s进行遍历
for sub_s in s.split():
    # 对子字符串sub_s根据"/"进行分割
    # 得到小朋友编号child，表示每位小朋友是否与前一位小朋友同班的字符"Y"或"N"
    child, ch = sub_s.split("/")
    # 分别储存child和ch
    children_lst.append(int(child))
    YN_lst.append(ch)

# 获得小朋友的数目
n = len(children_lst)

# 构建长度为n的dp数组，dp[i]的取值为True和False
# True表示第i个小朋友在1班，False表示第i个小朋友在2班
dp = [None] * n
# 初始化dp[0]为True，表示默认分配第0个小朋友在1班
dp[0] = True


# 遍历所有小朋友
for i in range(1, n):
    # 如果YN_lst[i]为"Y"，表示第i个小朋友和第i-1个小朋友同班
    # dp[i]和dp[i-1]取相同
    if YN_lst[i] == "Y":
        dp[i] = dp[i-1]
    # 如果YN_lst[i]为"N"，表示第i个小朋友和第i-1个小朋友不同班
    # dp[i]和dp[i-1]取相反
    elif YN_lst[i] == "N":
        dp[i] = not dp[i-1]


# 构建表示两个班级的列表
class1, class2 = list(), list()
for i in range(n):
    # 如果dp[i]为True，分到class1，如果dp[i]为False，分到class2
    class1.append(children_lst[i]) if dp[i] else class2.append(children_lst[i])


# 题目要求排序，故对class1和class2进行排序
class1.sort()
class2.sort()
# 如果class2长度为0，说明所有小朋友都在1班
# 输出1班的结果和一个空字符串
if len(class2) == 0:
    print(" ".join(map(str, class1)))
    print("")
else:
    # 两个班级之间的排序，以班级中编号最小的小朋友为准
    # 故如果发现2班编号最小的小朋友比1班编号最小的小朋友更小
    # 应该先输出2班，故对两者进行交换
    if class1[0] > class2[0]:
        class1, class2 = class2, class1
    # 先输出1班，再输出2班
    print(" ".join(map(str, class1)))
    print(" ".join(map(str, class2)))

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // 输入原始字符串数据
        String s = sc.nextLine();
        
        // 用于储存小朋友编号和"Y"/"N"标志
        List<Integer> children_lst = new ArrayList<>();
        List<Character> YN_lst = new ArrayList<>();

        // 对输入字符串以空格作为分割符的分割子字符串sub_s进行遍历
        String[] pairs = s.split(" ");
        for (String sub_s : pairs) {
            // 对子字符串sub_s根据"/"进行分割
            String[] parts = sub_s.split("/");
            int child = Integer.parseInt(parts[0]);
            char ch = parts[1].charAt(0);
            
            // 分别储存child和ch
            children_lst.add(child);
            YN_lst.add(ch);
        }

        // 获得小朋友的数目
        int n = children_lst.size();

        // 构建长度为n的dp数组，dp[i]的取值为true和false
        // true表示第i个小朋友在1班，false表示第i个小朋友在2班
        boolean[] dp = new boolean[n];

        // 初始化dp[0]为true，表示默认分配第0个小朋友在1班
        dp[0] = true;

        // 遍历所有小朋友
        for (int i = 1; i < n; i++) {
            // 如果YN_lst[i]为"Y"，表示第i个小朋友和第i-1个小朋友同班
            if (YN_lst.get(i) == 'Y') {
                dp[i] = dp[i - 1];
            }
            // 如果YN_lst[i]为"N"，表示第i个小朋友和第i-1个小朋友不同班
            else if (YN_lst.get(i) == 'N') {
                dp[i] = !dp[i - 1];
            }
        }

        // 构建表示两个班级的列表
        List<Integer> class1 = new ArrayList<>();
        List<Integer> class2 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (dp[i]) {
                class1.add(children_lst.get(i));
            } else {
                class2.add(children_lst.get(i));
            }
        }

        // 题目要求排序，故对class1和class2进行排序
        Collections.sort(class1);
        Collections.sort(class2);

        // 如果class2长度为0，说明所有小朋友都在1班
        if (class2.isEmpty()) {
            for (int i : class1) System.out.print(i + " ");
            System.out.println();
            System.out.println("");
        } else {
            // 两个班级之间的排序，以班级中编号最小的小朋友为准
            if (class1.get(0) > class2.get(0)) {
                List<Integer> temp = class1;
                class1 = class2;
                class2 = temp;
            }

            for (int i : class1) System.out.print(i + " ");
            System.out.println();
            for (int i : class2) System.out.print(i + " ");
            System.out.println();
        }

        sc.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

int main() {
    vector<int> children_lst;
    vector<char> YN_lst;

    // 输入原始字符串数据
    string s;
    getline(cin, s);

    // 对输入字符串以空格作为分割符的分割子字符串sub_s进行遍历
    stringstream ss(s);
    string sub_s;

    while (ss >> sub_s) {
        // 对子字符串sub_s根据"/"进行分割
        // 得到小朋友编号child，表示每位小朋友是否与前一位小朋友同班的字符"Y"或"N"
        size_t pos = sub_s.find('/');
        int child = stoi(sub_s.substr(0, pos));
        char ch = sub_s[pos + 1];

        // 分别储存child和ch
        children_lst.push_back(child);
        YN_lst.push_back(ch);
    }

    // 获得小朋友的数目
    int n = children_lst.size();

    // 构建长度为n的dp数组，dp[i]的取值为true和false
    // true表示第i个小朋友在1班，false表示第i个小朋友在2班
    vector<bool> dp(n);

    // 初始化dp[0]为true，表示默认分配第0个小朋友在1班
    dp[0] = true;

    // 遍历所有小朋友
    for (int i = 1; i < n; i++) {
        // 如果YN_lst[i]为"Y"，表示第i个小朋友和第i-1个小朋友同班
        // dp[i]和dp[i-1]取相同
        if (YN_lst[i] == 'Y') {
            dp[i] = dp[i - 1];
        }
        // 如果YN_lst[i]为"N"，表示第i个小朋友和第i-1个小朋友不同班
        // dp[i]和dp[i-1]取相反
        else if (YN_lst[i] == 'N') {
            dp[i] = !dp[i - 1];
        }
    }

    // 构建表示两个班级的列表
    vector<int> class1, class2;
    for (int i = 0; i < n; i++) {
        if (dp[i]) {
            class1.push_back(children_lst[i]);
        } else {
            class2.push_back(children_lst[i]);
        }
    }

    // 题目要求排序，故对class1和class2进行排序
    sort(class1.begin(), class1.end());
    sort(class2.begin(), class2.end());

    // 如果class2长度为0，说明所有小朋友都在1班
    if (class2.empty()) {
        for (int i : class1) cout << i << " ";
        cout << endl;
        cout << "" << endl;
    } else {
        // 两个班级之间的排序，以班级中编号最小的小朋友为准
        if (class1[0] > class2[0]) {
            swap(class1, class2);
        }

        for (int i : class1) cout << i << " ";
        cout << endl;
        for (int i : class2) cout << i << " ";
        cout << endl;
    }

    return 0;
}

C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 函数声明，用于比较两个整数的大小
int cmpfunc(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

// 用于交换两个数组的内容
void swap_classes(int class1[], int class2[], int *class1_size, int *class2_size) {
    int temp_class[1000];
    int temp_size = *class1_size;

    // 将 class1 的内容复制到临时数组中
    for (int i = 0; i < *class1_size; i++) {
        temp_class[i] = class1[i];
    }

    // 将 class2 的内容复制到 class1 中
    for (int i = 0; i < *class2_size; i++) {
        class1[i] = class2[i];
    }

    // 将临时数组中的内容复制到 class2 中
    for (int i = 0; i < temp_size; i++) {
        class2[i] = temp_class[i];
    }

    // 交换两个班级的大小
    int temp_class_size = *class1_size;
    *class1_size = *class2_size;
    *class2_size = temp_class_size;
}

int main() {
    char s[10000];
    fgets(s, 10000, stdin);

    int children_lst[1000], class1[1000], class2[1000];
    char YN_lst[1000];
    int n = 0;

    // 处理输入字符串，将小朋友的编号和是否同班的信息分开
    char *token = strtok(s, " ");
    while (token != NULL) {
        int child;
        char ch;

        sscanf(token, "%d/%c", &child, &ch);  // 解析子字符串
        children_lst[n] = child;              // 存储小朋友编号
        YN_lst[n] = ch;                       // 存储是否同班信息
        n++;
        token = strtok(NULL, " ");            // 获取下一个子字符串
    }

    // 初始化 dp 数组，dp[i] 表示第 i 个小朋友在 1 班 (1) 还是 2 班 (0)
    int dp[1000];
    dp[0] = 1;  // 第一个小朋友默认分配到 1 班

    // 遍历每个小朋友，依据 YN_lst 来判断是否同班
    for (int i = 1; i < n; i++) {
        if (YN_lst[i] == 'Y') {
            dp[i] = dp[i - 1];   // 同班
        } else if (YN_lst[i] == 'N') {
            dp[i] = !dp[i - 1];  // 不同班
        }
    }

    // 分配小朋友到 class1 或 class2
    int class1_size = 0, class2_size = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i]) {
            class1[class1_size++] = children_lst[i];  // 分配到 1 班
        } else {
            class2[class2_size++] = children_lst[i];  // 分配到 2 班
        }
    }

    // 对两个班的小朋友进行排序
    qsort(class1, class1_size, sizeof(int), cmpfunc);
    qsort(class2, class2_size, sizeof(int), cmpfunc);

    // 如果2班为空，直接输出1班
    if (class2_size == 0) {
        for (int i = 0; i < class1_size; i++) {
            printf("%d ", class1[i]);
        }
        printf("\n\n");
    } else {
        // 比较两个班级的第一个小朋友，决定输出顺序
        if (class1[0] > class2[0]) {
            swap_classes(class1, class2, &class1_size, &class2_size);  // 交换两个班级
        }

        // 输出1班
        for (int i = 0; i < class1_size; i++) {
            printf("%d ", class1[i]);
        }
        printf("\n");

        // 输出2班
        for (int i = 0; i < class2_size; i++) {
            printf("%d ", class2[i]);
        }
        printf("\n");
    }

    return 0;
}

Node JavaScript

const readline = require('readline');

// 创建接口读取输入
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 读取输入字符串
rl.question('', (s) => {
    const children_lst = [];
    const YN_lst = [];

    // 对输入字符串进行处理，分割子字符串sub_s
    s.split(' ').forEach(sub_s => {
        // 使用 "/" 分割每个子字符串
        const [child, ch] = sub_s.split('/');
        // 储存小朋友编号和是否同班的信息
        children_lst.push(parseInt(child));
        YN_lst.push(ch);
    });

    // 获得小朋友的数量
    const n = children_lst.length;

    // 初始化 dp 数组，存储每个小朋友是否在 1 班 (True) 还是 2 班 (False)
    const dp = new Array(n).fill(null);
    dp[0] = true; // 默认第一个小朋友在 1 班

    // 遍历所有的小朋友
    for (let i = 1; i < n; i++) {
        if (YN_lst[i] === 'Y') {
            dp[i] = dp[i - 1];  // 如果相邻小朋友同班
        } else if (YN_lst[i] === 'N') {
            dp[i] = !dp[i - 1]; // 如果相邻小朋友不同班
        }
    }

    // 初始化两个班级
    let class1 = [];
    let class2 = [];

    // 将小朋友分配到不同的班级
    for (let i = 0; i < n; i++) {
        if (dp[i]) {
            class1.push(children_lst[i]);  // 如果在 1 班
        } else {
            class2.push(children_lst[i]);  // 如果在 2 班
        }
    }

    // 排序两个班级
    class1.sort((a, b) => a - b);
    class2.sort((a, b) => a - b);

    // 如果2班为空，直接输出1班
    if (class2.length === 0) {
        console.log(class1.join(' '));
        console.log("");
    } else {
        // 检查是否需要交换班级输出顺序
        if (class1[0] > class2[0]) {
            [class1, class2] = [class2, class1];
        }
        // 输出两个班级
        console.log(class1.join(' '));
        console.log(class2.join(' '));
    }

    rl.close();
});

Go

package main

import (
        "bufio"
        "fmt"
        "os"
        "sort"
        "strconv"
        "strings"
)

func main() {
        // 用于读取输入数据
        scanner := bufio.NewScanner(os.Stdin)
        scanner.Scan()
        s := scanner.Text()

        // 定义两个切片来分别储存小朋友的编号和"Y"/"N"标志
        children_lst := []int{}
        YN_lst := []string{}

        // 对输入字符串以空格作为分割符的分割子字符串sub_s进行遍历
        for _, sub_s := range strings.Split(s, " ") {
                // 对子字符串sub_s根据"/"进行分割
                parts := strings.Split(sub_s, "/")
                // 将编号转换为整数并添加到children_lst
                child, _ := strconv.Atoi(parts[0])
                YN_lst = append(YN_lst, parts[1])
                children_lst = append(children_lst, child)
        }

        // 获得小朋友的数目
        n := len(children_lst)

        // 构建长度为n的布尔切片dp，dp[i]表示第i个小朋友所在的班级
        // true表示1班，false表示2班
        dp := make([]bool, n)
        // 初始化dp[0]为true，表示第0个小朋友在1班
        dp[0] = true

        // 遍历所有小朋友
        for i := 1; i < n; i++ {
                // 如果YN_lst[i]为"Y"，表示第i个小朋友和第i-1个小朋友同班
                if YN_lst[i] == "Y" {
                        dp[i] = dp[i-1] // dp[i]和dp[i-1]取相同
                } else if YN_lst[i] == "N" {
                        // 如果YN_lst[i]为"N"，表示第i个小朋友和第i-1个小朋友不同班
                        dp[i] = !dp[i-1] // dp[i]和dp[i-1]取相反
                }
        }

        // 构建表示两个班级的切片
        class1 := []int{}
        class2 := []int{}
        for i := 0; i < n; i++ {
                // 如果dp[i]为true，分到class1；否则分到class2
                if dp[i] {
                        class1 = append(class1, children_lst[i])
                } else {
                        class2 = append(class2, children_lst[i])
                }
        }

        // 题目要求排序，对class1和class2进行排序
        sort.Ints(class1)
        sort.Ints(class2)

        // 如果class2长度为0，说明所有小朋友都在1班
        if len(class2) == 0 {
                // 输出1班的结果和一个空字符串
                for i, v := range class1 {
                        if i > 0 {
                                fmt.Print(" ")
                        }
                        fmt.Print(v)
                }
                fmt.Println()
                fmt.Println()
        } else {
                // 两个班级之间的排序，以班级中编号最小的小朋友为准
                // 如果2班编号最小的小朋友比1班编号最小的小朋友更小，交换class1和class2
                if class1[0] > class2[0] {
                        class1, class2 = class2, class1
                }

                // 输出1班
                for i, v := range class1 {
                        if i > 0 {
                                fmt.Print(" ")
                        }
                        fmt.Print(v)
                }
                fmt.Println()

                // 输出2班
                for i, v := range class2 {
                        if i > 0 {
                                fmt.Print(" ")
                        }
                        fmt.Print(v)
                }
                fmt.Println()
        }
}

时空复杂度

时间复杂度：O(``xlogx + ylogy + N``)。O(xlogx)和O(ylogy)是两个班级各自排序的时间复杂度，O(N)是dp过程的时间复杂度。

空间复杂度：O(``N``)。

x和y为两个班级的人数，N是总人数。