Codeforces Round 923 (Div. 3) C. Choose the Different Ones(Java)

比赛链接：Round 923 (Div. 3)

C题传送门：C. Choose the Different Ones!

题目：

在这里插入图片描述
** Example**
** input**

6
6 5 6
2 3 8 5 6 5
1 3 4 10 5
6 5 6
2 3 4 5 6 5
1 3 8 10 3
3 3 4
1 3 5
2 4 6
2 5 4
1 4
7 3 4 4 2
1 4 2
2
6 4 4 2
1 5 2
3
2 2 1 4 3

output

YES 
NO
YES
YES
NO
NO

分析：

题目要我们判断从a[i]和b[i]中分别选k/2个元素，以便所选元素包含从 1 到 k 的每个整数。
我们可以定义3个变量cnt0，cnt1，com，每个相同数字只计算一次，cnt0是只存在a[i]中1-k整数的个数，cnt1是只存在b[i]中1-k整数的个数，com是共同存在a[i]和b[i]中1-k整数的个数。

定义二维数组b[k+10][2]，b[i][0]记录a[i]中1-k整数是否存在，b[i][1]记录b[i]中1-k整数是否存在，当b[i][0]==b[i][1]=1时，说明有共同的数。

最后我们通过cnt0，cnt1，com，k的数量关系可以判断结果。

代码：

import java.util.Scanner;public class Main {public static void main(String[] args) {   Scanner sc = new Scanner(System.in);int tt = sc.nextInt();while(tt-->0) {int n = sc.nextInt();int m = sc.nextInt();int k = sc.nextInt();int [][] b = new int [k+10][2];int cnt0 = 0;int cnt1 = 0;int com = 0;for(int i = 0;i < n;i++) {int t = sc.nextInt();if(t<=k&&b[t][0]==0) {b[t][0]=1;cnt0++;}}//System.out.println(cnt0);for(int i = 0;i < m;i++) {int t = sc.nextInt();if(t<=k&&b[t][1]==0) {b[t][1]=1;cnt1++;if(b[t][0]==1) {cnt0--;cnt1--;com++;}}}//System.out.println(cnt0+" "+cnt1+" "+com);if(cnt0+com<k/2||cnt1+com<k/2||cnt1+cnt0+com<k) {System.out.println("NO");}else if(com>0&&cnt0+com==k/2&&cnt1+com==k/2) {System.out.println("NO");}else {System.out.println("YES");}}}
}