最多能完成排序的块题解

1.题目：

题目描述： 数组arr是[0, 1, …, n - 1]的一种排列，我们将这个数组分割成几个“块”，并将这些块分别进行排序。之后再连接起来，使得连接的结果和按升序排序后的原数组相同。我们最多能将数组分成多少块？

输入：

5 5 4 3 2 1

输出：

1

2.分析：

这是一道神奇的贪心题，首先你要理解题目，题目要让你将这些数分成几块，比如【5，4】【3，2，1】然后你要保证对每个块中的数排序，最后可重组为排序后的原序列，最后让其块数最大。最后的贪心思路， 找到前i个数的最大值，然后和现在的真确序列中的第i个数比较，如果相同，就可以分一个块，此时sum++,最后输出sum。

3.证明：

当我们判断到此时最大值就为当前序列的数时，我们不难发现如果此时分一个块那么此时最大值一定会是在正确的位置上，因为之前有判断。除此之外细心的读者会发现：我只保证了最大值，但除最大值之外的这个块的其它数怎么办呢？其实我们显然不用考虑，因为在之前我们如果可以就已经将不符合原位置的数分了一块了，综上的证

4.代码：

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; int n, a[100005], b[100005], c[100005]; int main() { scanf("%d", &n); for(int i = 1;i <= n; i++) { scanf("%d", &a[i]); c[i] = a[i]; } sort(a + 1, a + 1 + n); int sum = 0, _max = 0; for(int i = 1;i <= n;i ++) { _max = max(_max, c[i]); if(_max == a[i]) { sum++; } } printf("%d", sum); }