【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 + " ");}}
}