51Nod-2502、2658 最多分成多少块 题解

最多分成多少块

最多分成多少块 V2

题目概述

给一个[0, n)的排列的数组，把这个数组分成若干块，对每块进行按升序排序，保证整个数组最后是升序的

问最多能分成几块

思路分析

容易想到的是，如果最后的数组是有序的，首先0应该在第一组中，0前面的元素都要放在第一组，同时因为给出的是一个排列，所以前i个元素排好序后应该刚好是[0, i)，即第一组中的所有数字应该恰好是[0, i)的一个排列

所以长度为i的前缀分成第一组的充要条件是：这个前缀的最小值为0，最大值为i

但是由于是一个排列，前i个元素中必定没有相等元素，前i个数的所以最大值为i时，最小值也一定为0

所以长度为i的前缀分成第一组的充要条件是：这个前缀的最大值为i

然后再继续思考：

现在有两个满足条件的前缀，一个长度为a，一个长度为b（a<b），那么他们可以被分成两组，第一组为[0,a)，第二组为[a,b)

因为[0, a)排好后，[0,b)的前a个是不动的

遍历数组，如果前i个元素的最大值为i，则组数+1

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long llong;
const int N = 2e5 + 5;
const int MOD = 1e9 + 7;
llong n, a[N];

int main() {
    #ifdef LOCAL
        freopen("D:/Code/ACM/in.in", "r", stdin);
        freopen("D:/Code/ACM/out.out", "w", stdout);
    #endif
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    llong mx = -1, ans = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        mx = max(mx, a[i]);
        if (mx == i) {
            ans++;
        }
    }
    cout << ans << "\n";
    return 0;
}