CodeForces599C【贪心】

题意： 给你一个序列,要求你从小到大排序,你可以划分成一个块一个块地进行块内排序,问你最多能分成几个块 思路： 贪心，首先感觉就是有正序的话我就分开啊； 难道倒序不能分块？321肯定不行啊。 存不存在连续两个倒序，但是后面有元素比前面块小，存在：[6 3] [5 1] 这样分成两块是错的。 所以首先是1，然后是2，然后是3，你可以标记啊，这个块有那么多元素，就是一段区间 比如第一个块，有n个元素的话，那么一定是[1,n]，然后就是模拟。 然后他的数组元素不是1-n范围的，那么先离散化一下。

注意：重复元素在离散化时，要按照坐标小优先；

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n; int a[N],dp[N]; struct asd{ int val; int id; }; asd q[N]; bool cmp(asd x,asd y){ if(x.val==y.val) return x.id<y.id; return x.val<y.val; } void init (){ sort(q+1,q+n+1,cmp); for(int i=1;i<=n;i++) dp[q[i].id]=i; // for(int i=1;i<=n;i++) // printf("%d ",dp[i]); } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); q[i].id=i; q[i].val=a[i]; } init(); int ans=0; int flag=0; int temp=0; for(int i=1;i<=n;i++) { if(flag<dp[i]) { flag=dp[i]; temp++; } else temp++; if(flag==temp) ans++; } printf("%d\n",ans); return 0; }