本文共 818 字，大约阅读时间需要 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最少划分为多少段排序子序列

输入例子:

61 2 3 2 2 1

输出例子:

2

分析：分成两种情况，递增区间与递减区间。还有在判断语句结束时有一个变量跳动，即当前指针应向下移动一位。

程序：

#include 
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long using namespace std;int solve(ll A[],int n){ if(n<=2){ return 1; } int p=0; int k=0; while(k!=n){ while(A[k]==A[k+1]){ ++k; } if(A[k]
          
           =A[k+1]){ ++k; } k+=1; p++; // cout<
           
<<" "; } } return p; }int main(int argc,char** argv){ ll N; while(cin>>N){ ll a[N]; for(int i=0;i
            
             >a[i]; } int len=solve(a,N); cout<
            
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/xiaochen87654321/article/details/72615565 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！