北京公司网站如何制作_嵌入式软件开发公司排名_网站友情链接查询_汕头网站建设方案推广

目录

牛客_排序子序列_模拟

题目解析

C++代码

Java代码

---

牛客_排序子序列_模拟

排序子序列_牛客笔试题_牛客网 (nowcoder.com)

描述：

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

---

题目解析

根据题意用指针模拟即可，直接放代码。

C++代码

#include <iostream>
#include <vector>
using namespace std;
int main()
{int n = 0, cnt = 0;cin >> n;vector<int> v(n + 1, 0); // 防止数组越界for (int i = 0; i < n; ++i){cin >> v[i];}for(int i = 1; i <= n; ++i) // n是判断最后一个元素单独为一个序列的情况{if(i == n - 1) // 数组不多开一个空间且 i != n的话就这样写{++cnt;break;}if(v[i] > v[i - 1]){while(i < n && v[i] >= v[i - 1]){++i;}++cnt;}else if(v[i] < v[i - 1]) // 注意不能直接写成if{while(i < n && v[i] <= v[i - 1]){++i;}++cnt;}else{while(i < n && v[i] == v[i - 1]){++i;}}}cout << cnt;return 0;
}

Java代码

import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[] arr = new int[n];for(int i = 0; i < n; i++) {arr[i] = in.nextInt();}int ret = 0, i = 0;while(i < n){if(i == n - 1){ret++;break;}if(arr[i] < arr[i + 1]){while(i + 1 < n && arr[i] <= arr[i + 1]) i++;ret++;}else if(arr[i] > arr[i + 1]){while(i + 1 < n && arr[i] >= arr[i + 1]) i++;ret++;}else{while(i + 1 < n && arr[i] == arr[i + 1]) i++;}i++;}System.out.println(ret);}
}