当前位置: 代码迷 >> 综合 >> 51nod 2658 最多分成多少块 V2 思维
  详细解决方案

51nod 2658 最多分成多少块 V2 思维

热度:94   发布时间:2024-01-15 06:19:27.0

2658 最多分成多少块 V2

  1. 1.0 秒
  2.  
  3. 131,072.0 KB
  4.  
  5. 10 分
  6.  
  7. 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;
}