2658 最多分成多少块 V2
- 1.0 秒
- 131,072.0 KB
- 10 分
- 2级题
小b有个长度为n的数组a,她想将这个数组排序。
然而小b很懒,她觉得对整个数组排序太累了,因此她请你将a分成一些块,使得她只需要对每一块分别排序,就能将整个数组排序。
请问你最多能把a分成多少块。
保证a为0...n-1的一个排列。
样例解释:
将a分成2块或者更多块,都无法得到所需的结果。
例如,分成 [4, 3], [2, 1, 0] ,排序得到的结果是 [3, 4, 0, 1, 2],这不是有序的数组。
收起
输入
第一行一个数n; 第二行n个数表示a[i],以空格隔开。 n<=100000
输出
输出一个数,对应问题的答案。
输入样例
5 0 1 2 4 3
输出样例
4
分析:
我们保存前面数的最大值,因为这题的数字是0~n,所以数字就是位置,如果当前位置和前面数的最大值相等,则可以分成一块。
#include <bits/stdc++.h>using namespace std;
int n,ans,d;
int s[100005];
int main()
{cin >> n;for(int i = 0;i < n;i ++){scanf("%d",&d);if(i!=0)s[i] = max(d,s[i - 1]);elses[i] = d;if(s[i] == i)ans++;}cout<<ans<<endl;
}