编程题——排序子序列

    xiaoxiao2022-07-05  175


    编程题——排序子序列


    题目描述: 牛牛定义排序子序列为一个数组中一段连续的子序列,并且这段子序列是非递增或者非递减排序的。牛牛有一个长度为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

    输入 4 1 3 2 3 输出 2

    示例2

    输入 4 1 3 3 2 输出 2

    示例3

    输入 5 1 2 1 2 1 输出 3


    程序代码如下:


    #include <iostream> #include <vector> using namespace std; /*最开始考虑使用波峰和波谷的特点,但是没有考虑到波峰和波谷的间距需要大于1 *比如输入: *4 *1 3 2 3 *输出:2 *应该输出2,但是实际输出的结果是3*/ /*为了避免a[i+1]越界,将数组定义为n+1个,a[n] = 0; *从0到n-1遍历数组,判断a[i]和a[i+1]: *如果是大于或小于,序列数+1,然后向后移动直到下一序列 *如果是等于,只向后移动*/ int main() { int n; int i = 0; while (cin >> n) { vector<int> a; a.resize(n+1);//设置数组长度为n+1来防止a[i+1]访问越界 long long num = 0; for (i = 0; i < n; ++i) { cin >> a[i]; } a[n] = 0; i = 0; while(i<n)//遍历数组 { if (a[i] < a[i + 1]) { while (i < n && a[i] <= a[i + 1]) //移动到当前序列末尾 i++; num++;//序列数+1 i++; //移动到下一序列 } else if (a[i] == a[i + 1]) i++; else { while (i < n && a[i] >= a[i + 1]) i++; num++; i++; } } cout << num << endl; } return 0; }

    程序运行结果如下:


    最新回复(0)