5、牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个数组分为几段排序子序列. 如样例所示,牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列,至少需要划分为2个排序子序列,所以输出2
牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为n的整数数组A,他现在有一个任务是把数组A分为若干段排序子序列,牛牛想知道他最少可以把这个数组分为几段排序子序列.
如样例所示,牛牛可以把数组A划分为[1,2,3]和[2,2,1]两个排序子序列,至少需要划分为2个排序子序列,所以输出2
输入描述:
输入的第一行为一个正整数n(1 ≤ n ≤ 10^5)
第二行包括n个整数A_i(1 ≤ A_i ≤ 10^9),表示数组A的每个数字。
输出描述:
输出一个整数表示牛牛可以将A最少划分为多少段排序子序列
输入例子:
6 1 2 3 2 2 1
输出例子:
2
思路：理解题目的子序列：即单调不具有极值
1 #include<stdio.h> 2 #include<stdlib.h> 3 #define n 10000 4 5 int N; 6 int A[n],res=0; 7 8 int up(int i)//非递减 9 { 10 while((i!=N-1)&&A[i]<=A[i+1]) 11 ++i; 12 return i; 13 } 14 15 int down(int i) //非递增 16 { 17 while((i!=N-1)&&A[i]>=A[i+1]) 18 ++i; 19 return i; 20 } 21 int main() 22 { 23 scanf("%d",&N); 24 for(int i=0;i<N;++i) 25 scanf("%d",&A[i]); 26 for(int i=0;i!=N;) 27 { 28 while(A[i]==A[i+1]) //相等就跳过 29 ++i; 30 if(A[i]<A[i+1]) 31 {i=up(i)+1; 32 ++res;} 33 else 34 {i=down(i)+1; 35 ++res;} 36 printf("i:%d res:%d ",i,res);//此题不需要这行 37 } 38 printf("%d",res); 39 }