Problem
小b有个长度为n的数组a，她想将这个数组排序。
然而小b很懒，她觉得对整个数组排序太累了，因此她请你将a分成一些块，使得她只需要对每一块分别排序，就能将整个数组排序。
请问你最多能把a分成多少块。
保证a为0...n-1的一个排列。
样例解释：
将a分成2块或者更多块，都无法得到所需的结果。 例如，分成 [4, 3], [2, 1, 0] ，排序得到的结果是 [3, 4, 0, 1, 2]，这不是有序的数组。
Solution
题目的意思是升序排，一种麻烦的思路是每添加一个数小于i就cur+1，否则进堆，每次看能否从堆中取出，cur==i时ans+1。
再仔细想，只需要前面出现的最大的数和当前i相等，ans就能+1。
Code1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
|
#include<stdio.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#include<stack>
#define mem(ss) memset(ss,0,sizeof(ss))
typedef long long ll;
typedef long double ld;
typedef __int128 lll;
const ll mod=1e9+7;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
inline int read(){int data=0;char ch=0;while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data;}
int n,x,ans,cur;
std::priority_queue<int,std::vector<int>,std::greater<int> >q;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&x);
int j=n-i-1;
while(!q.empty()&&q.top()<=i){
q.pop();
cur++;
}
if(x<=i){
cur++;
}
else{
q.push(x);
}
if(cur==i+1){
ans++;
}
}
printf("%d\n",ans);
return 0;
}
|
Code2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
#include<stdio.h>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#include<stack>
#define mem(ss) memset(ss,0,sizeof(ss))
typedef long long ll;
typedef long double ld;
typedef __int128 lll;
const ll mod=1e9+7;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
inline int read(){int data=0;char ch=0;while (ch<'0' || ch>'9') ch=getchar();while (ch>='0' && ch<='9') data=data*10+ch-'0',ch=getchar();return data;}
int n,x,ans,mx;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&x);
mx=std::max(x,mx);
if(mx==i)ans++;
}
printf("%d\n",ans);
return 0;
}
|