【day02】排序子序列_牛客网（贪心）

水深无声 2022-10-28 12:29 202阅读 0赞

# 排序子序列 #

## 题目描述 ##

题目链接：[排序子序列][Link 1]

牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。

牛牛有一个长度为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最少划分为多少段排序子序列

**示例1**

> 输入：
> 
>     6
>     1 2 3 2 2 1
> 
> 输出：
> 
>     2

**示例2**

> 输入：
> 
>     4 
>     1 3 2 3
> 
> 输出：
> 
>     2

**示例3**

> 输入：
> 
>     6 
>     3 2 1 1 2 3
> 
> 输出：
> 
>     2

## 解题思路及源码 ##

**思路：**

1.  本题依次比较整个数组
2.  如果a\[i+1\]>a\[i\] ，则进入非递增序列循环判断，直到遍历到下一个值不满足循环条件为止，退出循环后count++、i++
3.  如果a\[i+1\]<a\[i\]，则进入非递增序列循环判断，直到遍历到下一个值不满足循环条件为止，退出循环后count++，i++
4.  如果a\[i+1\] == a\[i\]，i++进行下一位置遍历，因为相等既可以属于非递增序列，也可以属于非递减序列。

**本题注意点**：本题开始比较a\[i+1\]与a\[i\]进行比较，为了避免越界，数组定义为n+1个，同时给a\[n\] = 0;  
a\[n\] = 0带来的影响，我们分为三种情况讨论：

1.  若到a\[n-1\] 的最后一组是非递减序列，当i==n-1，a\[i\] >a\[i+1\]，因为前面的数都是大于0的，这个输入条件已经说明了(去看看题目输入条件描述)，里面的循环结束，i++，count++，i==n，外面的循环结束。
2.  若到a\[n-1\] 的最后一组是非递增序列，当i==n-1，a\[i\] >a\[i+1\]，因为前面的数都是大于0的，这个输入条件已经说明了(去看看题目输入条件描述)，循环再走一次，i++， i== n，里面的循环结束，i++，count++，i==n+1，外面的循环结束。
3.  第三种情况 1 2 1 2 1最后一个数是单独的情况，后面补个0，序列变成1 2 1 2 1 0，当走完全面的序列i==n-1时，a\[i\] > a\[i+1\],进入判断出一个非递增序列，count++，i++,循环结束。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]

**提醒**：非递减就是a\[i\]<=a\[i+1\]，递减就是a\[i\]>a\[i+1\]，非递增就是a\[i\]>=a\[i+1\]，递增就是a\[i\]<a\[i+1\]

**解法一：**

#include <iostream>
    #include <vector>
    using namespace std;
    
    int main()
    { 
        int n;
        cin >> n;
        // 1.数据处理
        vector<int> v;
        v.resize(n + 1);
        v[n] = 0;
        for(int i = 0; i < n; i++)
            cin >> v[i];
        //2.统计增减序列
        int ans = 0;
        int index = 0;
        while(index < n)
        { 
            if(v[index] < v[index + 1])
            { 
                //下面的=是为了处理增减序列中出现相等的情况,例如 1 2 2 3
                while(index < n && v[index] <= v[index + 1])
                    index++;
                ans++;
            }
            else if(v[index] > v[index + 1])
            { 
                //下面的=是为了处理增减序列中出现相等的情况,例如 3 2 2 1
                while(index < n && v[index] >= v[index + 1])
                    index++;
                ans++;
            }
            // 处理下面情况：1 2 2 2 2 1
            index++;
        }// end while
        cout << ans << endl;
        return 0;
    }
         ans++;
            }
            // 处理下面情况：1 2 2 2 2 1
            index++;
        }// end while
        cout << ans << endl;
        return 0;
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/2d3f6ddd82da445d804c95db22dcc471?f=discussion
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNzAyMg_size_16_color_FFFFFF_t_70]: /images/20221024/c3b432c301b74b638011ceee7c428d18.png