html5 素材网站,网站和数字界面设计师,去哪接单做网站,推广广告赚钱题干#xff1a;
给定一个数列A#xff0c;要求你将这个数列划分成几个连续的部分#xff0c;使得每部分分别从小到大排序后整个数列有序。
问最多可以划分成几个部分。
Input
第一行包含一个整数 n (1 ≤ n ≤ 100 000) — 表示数列的长度
之后一行 n 个整数 hi …题干
给定一个数列A要求你将这个数列划分成几个连续的部分使得每部分分别从小到大排序后整个数列有序。
问最多可以划分成几个部分。
Input
第一行包含一个整数 n (1 ≤ n ≤ 100 000) — 表示数列的长度
之后一行 n 个整数 hi (1 ≤ hi ≤ 109). 描述这个数列。
Output
输出最多能划分出的部分数。
Example
Input
3
1 2 3Output
3Input
4
2 1 3 2Output
2解题报告 做法很多标解是用一个排序然后对排序前后的数组的差做前缀和如果前缀和是0则说明可以断开反之则不能断开。 这题也可以贪心考虑能分区间则分一段所以对于每一个数先找到比他小的最右边的数这个可以map维护最右下标然后二分来得到然后对这中间的数也找比他小的最右下标在维护一个最大值那么就在之类分段。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includestack
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define FF first
#define SS second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
ll sum,ans,n,a[MAX],b[MAX];
int main()
{cinn;for(int i 1; in; i) {scanf(%lld,ai);b[i]a[i];}sort(b1,bn1);for(int i 1; in; i) {sum a[i]-b[i];if(sum 0) ans;}cout ans endl;return 0 ;
}
