题目描述
给定两个数组 a 和 b,每个数组中都包含 n 个正整数。
再给定一个整数 x。
请你判断,能否通过重新排列 b 中的元素,使得 ai+bi≤x 对于每个 i(1≤i≤n)成立。
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据第一行包含两个整数 n 和 x。
第二行包含 n 个整数 a1,a2,…,an。
第三行包含 n 个整数 b1,b2,…,bn。
注意,两个数组内的元素都是以非降序的顺序给出。
每组数据之间,用空行隔开。
输出格式
每组数据输出一行结果,如果能够通过重新排列 b 中的元素,使得 ai+bi≤x 对于每个 i(1≤i≤n)成立,则输出 Yes,否则输出 No。
1≤T≤100,
1≤n≤50,
1≤x≤1000,
1≤a1≤a2≤…≤an≤x,
1≤b1≤b2≤…≤bn≤x
样例
输入样例:
4
3 4
1 2 3
1 1 2
2 6
1 4
2 5
4 4
1 2 3 4
1 2 3 4
1 5
5
5
输出样例:
Yes
Yes
No
No
算法1
根据贪心原理-> 题目说注意,两个数组内的元素都是以非降序的顺序给出。
即都是从小到大的,而且我们要满足$$ ai+bi≤x 对于每个 i(1≤i≤n)成立$$
所以我们只要一个正着排,一个倒着排,然后将a[i] + b[i]
加起来只要都
小于$$“x”$$就可以了
C++ 代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e3;
int a[N],b[N];
bool flag;
bool cmp(int x,int y){
return x > y;
}
int main(){
int T;
scanf("%d",&T);
while(T --){
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);
flag = true;
int n,x;
scanf("%d%d",&n,&x);
for(int i = 1;i <= n;i ++) scanf("%d",&a[i]); //正着排
sort(a + 1,a + n + 1);
for(int i = 1;i <= n;i ++) scanf("%d",&b[i]); //倒着排
sort(b + 1,b + n + 1, cmp);
for(int i = 1;i <= n;i ++){
if(a[i] + b[i] > x)
flag = false;
}
if(flag) puts("Yes");
else puts("No");
}
}