【c++笔试强训】（第四十二篇）

目次

排序⼦序列（模仿）
标题分析
讲授算法原理
编写代码
淘汰整数（贪⼼）
标题分析
讲授算法原理
编写代码

---

排序⼦序列（模仿）

标题分析

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++算法代码：

1. #include <iostream>
2. using namespace std;
3. const int N = 1e5 + 10;
4. int n;
5. int arr[N];
6. int main()
7. {
8. cin >> n;
9. for(int i = 0; i < n; i++) cin >> arr[i];
10. int ret = 0, i = 0; while(i < n)
11. {
12. if(i == n - 1)
13. {
14. ret++;
15. break;
16. }
17. if(arr[i] < arr[i + 1])
18. {
19. while(i + 1 < n && arr[i] <= arr[i + 1]) i++; ret++;
20. }
21. else if(arr[i] > arr[i + 1])
22. {
23. while(i + 1 < n && arr[i] >= arr[i + 1]) i++; ret++;
24. }
25. else
26. {
27. while(i + 1 < n && arr[i] == arr[i + 1]) i++;
28. }
29. i++;
30. }
31. cout << ret << endl;
32. return 0;
33. }

复制代码

java算法代码：

1. import java.util.Scanner;
2. // 注意类名必须为 Main, 不要有任何 package xxx 信息
3. public class Main
4. {
5. public static void main(String[] args)
6. {
7. 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();
8. }
9. int ret = 0, i = 0; while(i < n)
10. {
11. if(i == n - 1)
12. {
13. ret++; break; }
14. if(arr[i] < arr[i + 1])
15. {
16. while(i + 1 < n && arr[i] <= arr[i + 1]) i++; ret++;
17. }
18. else if(arr[i] > arr[i + 1])
19. {
20. while(i + 1 < n && arr[i] >= arr[i + 1]) i++; ret++;
21. }
22. else
23. {
24. while(i + 1 < n && arr[i] == arr[i + 1]) i++;
25. }
26. i++;
27. }
28. System.out.println(ret);
29. }
30. }

复制代码

淘汰整数（贪⼼）

标题分析

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++算法代码：

1. #include <iostream>
2. using namespace std;
3. int t, h;
4. int fun()
5. {
6. int ret = 0, a = 1;
7. while(h)
8. {
9. h -= a;
10. ret++;
11. if(h % (a * 2) == 0)
12. {
13. a *= 2;
14. }
15. }
16. return ret;
17. }
18. int main()
19. {
20. cin >> t;
21. while(t--)
22. {
23. cin >> h;
24. cout << fun() << endl;
25. }
27. return 0;
28. }

复制代码

java算法代码：

1. import java.util.*;
2. public class Main
3. {
4. public static void main(String[] args)
5. {
6. Scanner in = new Scanner(System.in); int t = in.nextInt(); while(t-- != 0)
7. {
8. int h = in.nextInt(); int ret = 0, a = 1; while(h != 0)
9. {
10. h -= a; ret++; if(h % (a * 2) == 0) {
11. a *= 2;
12. }
13. }
14. System.out.println(ret);
15. }
16. }
17. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。