【c++笔试强训】（第三十篇）
目录
爱丽丝的⼈偶（贪⼼+构造）
题目解析
讲解算法原理
编写代码
集合（排序）
题目解析
讲解算法原理
编写代码
爱丽丝的⼈偶（贪⼼+构造）
题目解析
1.题目链接：登录—专业IT笔试面试备考平台_牛客网
2.题目描述
题目描述
爱丽丝有n n\ n 个人偶，每个人偶的身高依次是1、2、3……n 1、2、3……n\ 1、2、3……n
现在她要将这n n\ n 个人偶摆成一排。
但是人偶被设置了魔法。假设对一个非两端的（不在队首也不在队尾）人偶x x\ x 而言，她相邻的两个人偶，一个比x x\ x 高、一个比x x\ x 矮，那么x x\ x 就会爆炸。
爱丽丝想找到一种摆法，使得所有人偶都不会爆炸。你能帮帮她吗？
输入描述:
一个正整数n n\ n (3≤n≤100000) (3≤n≤100000)\ (3≤n≤100000)
输出描述:
满足要求的一种摆法。如果有多解，输出任意一种摆法即可。
示例1
输入
3
3
输出
1 3 2
1 3 2
说明
对于第二个人偶，她两边的两个人偶都比她矮，满足要求。
另外，[3 1 2]、 [2 1 3] 、[2 3 1]这三种摆法也都满足要求。输出这三种摆法也视为正确。
讲解算法原理
解法：
算法思路：
放个⼩的之后，再放个⼤的~
编写代码
c++算法代码：
#include <iostream>
using namespace std;
int n;
int main()
{cin >> n;int left = 1, right = n;while(left <= right){cout << left << " "; left++; if(left <= right) { cout << right << " "; right--;}}return 0;
}java算法代码：
import java.util.*;
public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in); int n = in.nextInt();int left = 1, right = n; while(left <= right) {System.out.print(left + " "); left++; if(left <= right){System.out.print(right + " "); right--;}}}
}集合（排序）
题目解析
1.题目链接：集合_牛客题霸_牛客网
2.题目描述
描述
给你两个集合，要求{A} + {B}。 注：同一个集合中不会有两个相同的元素。
输出时按数字升序输出。
数据范围： 1 \le n, m \le 10000 \1≤n,m≤10000 ，集合中的元素满足 1 \le val \le 10^5 \1≤val≤105
输入描述：
每组输入数据分为三行,第一行有两个数字n,m，分别表示集合A和集合B的元素个数。后两行分别表示集合A和集合B。每个元素为不超过int范围的整数,每个元素之间有个空格隔开。
输出描述：
针对每组数据输出一行数据，表示合并后的集合，要求从小到大输出，每个元素之间有一个空格隔开,行末无空格。
示例1
输入：
3 3
1 3 5
2 4 6复制输出：
1 2 3 4 5 6
复制
示例2
输入：
2 2
1 2
1 2复制输出：
1 2
讲解算法原理
解法：
算法思路：
什么？笔试题？我直接set⾛起！
编写代码
c++算法代码：
#include <iostream>
#include <set>
using namespace std;
int main()
{int n, m;cin >> n >> m;int x;set<int> s;for(int i = 0; i < n; i++){cin >> x;s.insert(x);}for(int i = 0; i < m; i++){cin >> x;s.insert(x);}for(auto x : s){cout << x << " ";}return 0;
}Java算法代码：
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{public static void main(String[] args) {Scanner in = new Scanner(System.in); int n = in.nextInt(), m = in.nextInt();TreeSet<Integer> set = new TreeSet<>(); int x; while(n-- != 0){x = in.nextInt(); set.add(x);}while(m-- != 0){x = in.nextInt(); set.add(x);}for(int a : set){System.out.print(a + " ");}}
}