目录
排序⼦序列（模拟）
题目解析
讲解算法原理
编写代码
削减整数（贪⼼）
题目解析
讲解算法原理
编写代码
排序⼦序列（模拟）
题目解析
1.题目链接：排序子序列_牛客笔试题_牛客网
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最少划分为多少段排序子序列
示例1
输入
6
1 2 3 2 2 1输出
2
讲解算法原理
解法：
算法思路：
根据题意，⽤指针模拟即可。
（注意：本道题的测试数据不严谨，有可能错误的代码也能提交过~）
编写代码
c++算法代码：
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
int arr[N];
int main()
{cin >> n;for(int i = 0; i < n; i++) cin >> arr[i];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++;}cout << ret << endl;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);}
}削减整数（贪⼼）
题目解析
1.题目链接：登录—专业IT笔试面试备考平台_牛客网
2.题目描述
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
给出一个正整数H，从1开始减，第一次必须减1，每次减的数字都必须和上一次相同或者是上一次的两倍，请问最少需要几次能把H恰好减到0。
输入描述:
第一行给出一个正整数T{T}T，1≤T≤1041 \le T \le 10^41≤T≤104
接下来T行每行一个H,1≤H≤109H,1 \le H \le 10^9H,1≤H≤109
输出描述:
每行一个正整数代表最少的次数
示例1
输入
3 3 5 7
3
3
5
7输出
2 3 3
2
3
3
讲解算法原理
解法：
算法思路：
贪⼼+数学。
a. 尽可能的翻倍；
b. 不能⽆脑翻倍，只能是 2 * cur 的倍数时，才能翻倍。
编写代码
c++算法代码：
#include <iostream>
using namespace std;
int t, h;
int fun()
{int ret = 0, a = 1;while(h){h -= a;ret++;if(h % (a * 2) == 0){a *= 2;}}return ret;
}
int main()
{cin >> t;while(t--){cin >> h;cout << fun() << endl;}return 0;
}java算法代码：
import java.util.*;
public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in); int t = in.nextInt(); while(t-- != 0){int h = in.nextInt(); int ret = 0, a = 1; while(h != 0){h -= a; ret++; if(h % (a * 2) == 0) {a *= 2;}}System.out.println(ret);}}
}
