首页 > 试题广场 >

小美的数组重排

[编程题]小美的数组重排
  • 热度指数:1015 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小美有两个长度为n的数组ab
小美想知道,能不能通过重排a数组使得对于任意1 \leq i \leq n,1 \leq a_i + b_ i \leq m
将会有q次询问。

输入描述:
第一行一个整数q(1 \leq q \leq 30)。表示询问次数。
对于每一个询问:
第一行输入两个整数n,m(1 \leq n,m \leq 500)
第二行输入n个整数a_i(-500 \leq a_i \leq 500)
第三行输入n个整数b_i(-500 \leq b_i \leq 500)


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

输入

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]时满足条件。
import java.util.*;
/*
基本思路:
1、因只需要判断存在性,故可直接寻找边界条件
2、对a、b进行排序
3、当(a[n-i-1] + b[i])不在[1,m]中时,即可判定No
4、遍历完后,一定存在至少一种重排方法,所以可判定为Yes
 */
public class Main {
    public static Integer[] sort(Integer[] nums){
        Arrays.sort(nums, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2){
                return o1 - o2;
            }
        });
        return nums;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        for(int i = 0; i < q; i++){
            int n = in.nextInt();
            int m = in.nextInt();
            Integer[] a = new Integer[n];
            Integer[] b = new Integer[n];
            for(int j = 0; j < n; j++){
                a[j] = in.nextInt();
            }
            for(int j = 0; j < n; j++){
                b[j] = in.nextInt();
            }
            a = sort(a);
            b = sort(b);
            int d;
            for(d = 0; d < n; d++){
                int value = a[n-d-1] + b[d];
                if(value < 1 || value > m){
                    System.out.println("No");
                    break;
                }
            }
            if(d == n){
                System.out.println("Yes");
            }

        }
    }
}


编辑于 2024-04-18 23:53:10 回复(0)