解题思路

题意：给定一组正整数，允许把数组切成若干连续的“块”，对每一块单独排序后再按原顺序拼接，要求拼接后的整个数组是从小到大有序，问最多能切成多少块。

核心想法：

• 设在位置 i 后面切一刀（左边是 0..i 这一块，右边是 i+1..n-1）。
• 若想切在这里合法，那么左边块里最大的数一定不能大于右边所有数中最小的数，否则排序后左块仍会有元素比右块大，拼接后整体不会有序。
• 因此，切分条件是： max( arr[0..i] ) <= min( arr[i+1..n-1] )

实现步骤（贪心 + 前后缀预处理）：

1. 预处理前缀最大数组 preMax[i] = max(arr[0..i])。

2. 预处理后缀最小数组 sufMin[i] = min(arr[i..n-1])。

3. 从左到右枚举每个可能的切点 i = 0..n-2：

   • 如果 preMax[i] <= sufMin[i+1]，说明可以在 i 后面切一刀，块数加一。

4. 最终块数 = “合法切点数 + 1”。（至少有一块）

复杂度分析

• 时间复杂度：

  • 计算前缀最大 O(n)，
  • 计算后缀最小 O(n)，
  • 扫描所有切点 O(n)， 整体为 O(n)。

• 空间复杂度：

  • 需要两个长度为 n 的辅助数组 preMax 和 sufMin， 故为 O(n)。

在 n ≤ 500 的数据范围内完全足够。

代码实现

Python

import sys

# 功能函数：计算最多能分成多少块
def max_chunks(arr):
    n = len(arr)
    if n == 0:
        return 0

    # 前缀最大值
    pre_max = [0] * n
    cur = arr[0]
    for i in range(n):
        if arr[i] > cur:
            cur = arr[i]
        pre_max[i] = cur

    # 后缀最小值
    suf_min = [0] * n
    cur = arr[-1]
    for i in range(n - 1, -1, -1):
        if arr[i] < cur:
            cur = arr[i]
        suf_min[i] = cur

    # 统计合法切点
    cnt = 0
    for i in range(n - 1):
        if pre_max[i] <= suf_min[i + 1]:
            cnt += 1

    return cnt + 1  # 块数 = 切点数 + 1


def main():
    # 读取所有整数，视为一个数组
    data = sys.stdin.read().split()
    if not data:
        return
    arr = list(map(int, data))

    ans = max_chunks(arr)
    print(ans)


if __name__ == "__main__":
    main()

Java

import java.util.*;

// ACM 风格主类
public class Main {

    // 功能函数：计算最多能分成多少块
    public static int maxChunks(int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;

        int[] preMax = new int[n]; // 前缀最大值
        int[] sufMin = new int[n]; // 后缀最小值

        // 计算前缀最大值
        int cur = arr[0];
        for (int i = 0; i < n; i++) {
            if (arr[i] > cur) cur = arr[i];
            preMax[i] = cur;
        }

        // 计算后缀最小值
        cur = arr[n - 1];
        for (int i = n - 1; i >= 0; i--) {
            if (arr[i] < cur) cur = arr[i];
            sufMin[i] = cur;
        }

        // 统计合法切点
        int cnt = 0;
        for (int i = 0; i < n - 1; i++) {
            if (preMax[i] <= sufMin[i + 1]) {
                cnt++;
            }
        }

        return cnt + 1; // 块数 = 切点数 + 1
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> list = new ArrayList<>();

        // 读入所有整数，视为一个数组
        while (sc.hasNextInt()) {
            list.add(sc.nextInt());
        }
        sc.close();

        if (list.isEmpty()) return;

        int n = list.size();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = list.get(i);
        }

        int ans = maxChunks(arr);
        System.out.println(ans);
    }
}

C++

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

// 功能函数：计算最多能分成多少块
int maxChunks(const vector<int>& arr) {
    int n = (int)arr.size();
    if (n == 0) return 0;

    vector<int> preMax(n), sufMin(n);

    // 计算前缀最大值
    int cur = arr[0];
    for (int i = 0; i < n; ++i) {
        if (arr[i] > cur) cur = arr[i];
        preMax[i] = cur;
    }

    // 计算后缀最小值
    cur = arr[n - 1];
    for (int i = n - 1; i >= 0; --i) {
        if (arr[i] < cur) cur = arr[i];
        sufMin[i] = cur;
    }

    // 统计合法切点
    int cnt = 0;
    for (int i = 0; i < n - 1; ++i) {
        if (preMax[i] <= sufMin[i + 1]) {
            ++cnt;
        }
    }

    return cnt + 1; // 块数 = 切点数 + 1
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<int> arr;
    int x;

    // 读入所有整数，视为一个数组
    while (cin >> x) {
        arr.push_back(x);
    }

    if (arr.empty()) return 0;

    int ans = maxChunks(arr);
    cout << ans << "\n";

    return 0;
}

题目内容

两队学生拿着号码牌，排成 $1$ 队，选择队伍中连续的几个学生将他们按照号码牌就地 升序 排序之后连接起来，使得连接的结果和直接整体按升序排列后的结果一致

输入描述

一组正整数数组

如：$5$ $4$ $3$ $2$ $1$，数组长度为【$1,500$】

输出描述

最多将学生分成多少块

样例1

输入

2 1 3 4 4 5

输出

5

说明

分成 $[2,1],[3],[4],[4],[5]$ 可以得到最多的块数。

样例2

输入

5 4 3 2 1

输出

1

说明

将数组分成 $2$ 块或者更多块，都无法得到所需的结果。

例如，分成 $[5,4],[3,2,1]$ 的结果是 $[4, 5,1,2,3]$，这不是有序的数组。