大厂秋招真题【贪心】美团20230826秋招T2-小美的数组重排

【贪心】美团2023秋招-小美的数组重排

题目描述与示例

题目描述

小美有两个长度为n的数组a和b。

小美想知道，能不能通过重排a数组使得对于任意1 <= i <= n, 1 <= ai+bi <= m？

将会有q次询问。

输入描述

第一行一个整数q (1 <= q <= 30)。表示询问次数。

对于每一个询问：

第一行输入两个整数n, m (1 <= n, m <= 500)

第二行输入n个整数ai (-500 <= ai <= 500)

第三行输入n个整数bi (-500 <= bi <= 500)

输出描述

q行，每行输出一个字符串，如果能通过重排满足条件则输出"Yes"(不含引号)，否则输出"No"。

示例

输入

2
5 3
-1 -2 3 4 5
-1 3 4 2 5
5 6
-1 -2 3 4 5
-1 3 4 2 5

输出

No
Yes

说明

对于第一个用例，无论怎么重排都不满足条件。

对于第二个用例，将数组a重排为[5,3,-2,4,-1]时满足条件。

解题思路

注意，本题和LeetCode881. 救生艇 的思路非常相似。

贪心地思考问题，首先选择a数组中的最小值和b数组中的最大值相加，若结果不满足1 <= ai+bi <= m，如

• ai+bi > m，则说明b数组中的最大值太大，a数组中选择其他值与b中的最大值相加更不可能满足条件
• ai+bi < 1，则说明a数组中的最小值太大，b数组中选择其他值与a中的最小值相加更不可能满足条件

若上述结果满足1 <= ai+bi <= m，则同样地考虑a中的次小值，b中的次大值，依次类推。

故我们只需要对a数组和b数组分别进行升序和降序排序，考虑同一位置的两个元素相加是否满足1 <= ai+bi <= m即可。

代码

Python

# 题目：【贪心】美团2023秋招-小美的数组重排
# 作者：闭着眼睛学数理化
# 算法：贪心/排序
# 代码有看不懂的地方请直接在群上提问# 对于每组询问，求解的函数
def solve(n, m, a, b):# 对a升序排序，对b逆序排序a.sort()b.sort(reverse = True)# 遍历a和b中同一位置的元素for i in range(n):# 若同一个位置的元素相加大于m，# 则无法满足重排要求，返回"No"if a[i] + b[i] > m or a[i] + b[i] < 1:return "No"# 若成功退出循环，则返回"Yes"return "Yes"# 询问次数q
q = int(input())
ans = list()for _ in range(q):# 对于每一次询问，输入三行# 分别为数组长度n，整数m，数组a和bn, m = map(int, input().split())a = list(map(int, input().split()))b = list(map(int, input().split()))ans.append(solve(n, m, a, b))for s in ans:print(s)

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int q = scanner.nextInt();List<String> ans = new ArrayList<>();for (int t = 0; t < q; t++) {int n = scanner.nextInt();int m = scanner.nextInt();int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();}int[] b = new int[n];for (int i = 0; i < n; i++) {b[i] = scanner.nextInt();}ans.add(solve(n, m, a, b));}for (String s : ans) {System.out.println(s);}}private static String solve(int n, int m, int[] a, int[] b) {List<Integer> aList = new ArrayList<>();List<Integer> bList = new ArrayList<>();for (int num : a) {aList.add(num);}for (int num : b) {bList.add(num);}Collections.sort(aList);Collections.sort(bList, Collections.reverseOrder());for (int i = 0; i < n; i++) {if (aList.get(i) + bList.get(i) > m || aList.get(i) + bList.get(i) < 1) {return "No";}}return "Yes";}
}

C++

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;string solve(int n, int m, vector<int>& a, vector<int>& b) {sort(a.begin(), a.end());sort(b.begin(), b.end(), greater<int>());for (int i = 0; i < n; i++) {if (a[i] + b[i] > m || a[i] + b[i] < 1) {return "No";}}return "Yes";
}int main() {int q;cin >> q;vector<string> ans;for (int t = 0; t < q; t++) {int n, m;cin >> n >> m;vector<int> a(n);for (int i = 0; i < n; i++) {cin >> a[i];}vector<int> b(n);for (int i = 0; i < n; i++) {cin >> b[i];}ans.push_back(solve(n, m, a, b));}for (const string& s : ans) {cout << s << endl;}return 0;
}

时空复杂度

时间复杂度：O(NlogN)。排序所需的时间复杂度。

空间复杂度：O(1)。不考虑排序所需要的空间，只需要若干常数变量。

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多