小美想知道,能不能通过重排
将会有
第一行一个整数。表示询问次数。
对于每一个询问:
第一行输入两个整数。
第二行输入个整数
。
第三行输入个整数
。
行,每行输出一个字符串,如果能通过重排满足条件则输出"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
对于第一个用例,无论怎么重排都不满足条件。
对于第二个用例,将数组重排为[5,3,-2,4,-1]时满足条件。
import java.util.*; import java.io.*; import java.math.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) throws Exception { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int q = Integer.parseInt(bf.readLine()); for(int i=0;i<q;i++){ String[] str = bf.readLine().split(" "); int n = Integer.parseInt(str[0]); int m = Integer.parseInt(str[1]); int[] numsa = new int[n]; Integer[] numsb = new Integer[n]; str = bf.readLine().split(" "); for(int j=0;j<n;j++){ numsa[j]=Integer.parseInt(str[j]); } str = bf.readLine().split(" "); for(int j=0;j<n;j++){ numsb[j]=Integer.parseInt(str[j]); } Arrays.sort(numsa); Arrays.sort(numsb, Collections.reverseOrder()); boolean res=true; for(int j=0;j<n;j++){ int sum = numsa[j]+numsb[j]; //System.out.println("numsa="+numsa[j]+",numsb="+numsb[j]+",i="+j+",sum="+sum); if(sum>=1 && sum <=m){ continue; } else{ res=false; break; } } System.out.println(res ? "Yes" : "No"); } } }
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"); } } } }
def solve(n, m, a, b): """ :param n: int, 数组的长度 :param m: int, :param a: List[int], 数组 a :param b: List[int], 数组 b """ a.sort() b.sort(reverse=True) for ai, bi in zip(a, b): if not 1 <= ai+bi <= m: return False return True q = int(input()) for _ in range(q): n, m = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split())) print("Yes" if solve(n, m, a, b) else "No")