题目描述

小蓝有 N 个小球，编号 1 至 N。其中 N − 1 是正品，重量相同；有 1 个是次品，重量比正品轻。

为了找出次品，小蓝已经用天平进行了 M 次称重，并且记录下来每次两边放的小球编号，和称重结果。

请你根据记录，判断还剩下几个小球有次品的嫌疑。

输入格式

第一行包含 2 个整数 N 和 M。

以下包含 M 次称重记录，每个记录占 4 行。

第一行是一个整数 K，表示天平两边各放了 K 个小球。

第二行包含 K 个整数，代表放在天平左边的小球编号。

第三行包含 K 个整数，代表放在天平右边的小球编号。

第四行是一个字符，为 ‘>’, ‘<’, ‘=’ 之一。‘>’ 代表左边比右边重，‘<’ 代表左边比右边轻，‘=’ 代表两边重量相等。

在一次称重中保证每个小球最多出现 1 次。

输出格式

输出一个整数，代表答案。

样例输入

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

=

样例输出

2

思路：自己写的代码实在不会优化了，还是超时。先说下思路，思路绝对没问题，因为我看见有人用了这个思路过了，除了我没用三元运算符，其他的都差不多。次品小球轻，那么每次对比，那方比较轻，次品就在那一堆里面。一开始会想，遍历一遍，看看轻的那一份有几个小球就行了。但要考虑到放的小球是否之前已经放过，还有假设称重的结果全部都为等于，那得出的结果就是0，这是明显不对的， 最后，假设我们有这样一个样例
10 3
3
1 2 3
4 5 6
<
2
3 7
8 9

=
1
1
10
<

先梳理一下，称重第一次，次品在1 2 3中，称重第二次，等于，都是正品。称重第三次，1是次品。若我们只看轻的那一方的数量，结果为3而不是一，也就是因为第三次称重影响了第一次称重的结果。
因为1轻，所以可以证明第一次称重中 2 3不是次品。
思路清晰了。
代码晾上

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;public class Main {static int N =  2000005;static int mod = 1000000007;static Map map = new HashMap<>();static Map map2 = new HashMap<>();static int cnt=0;static int n=0;static int sum=0;static boolean flag = false;static double res = 9999999;static int a[] = new int[N];static int b[] = new int[N];static int dirx[] ={-1,0,1,0};static int diry[] ={0,1,0,-1};static Set set = new TreeSet<>();public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n =sc.nextInt();int m=sc.nextInt();for(int i=0;iint k = sc.nextInt();for(int j=0;jfor(int j=0;jset.add(a[j]);set.add(b[j]);}}else{if(str.equals(">")){for(int j=0;jset.add(a[j]);map.put(b[j], map.getOrDefault(b[j], 0)+1);}}else{for(int j=0;jset.add(b[j]);map.put(a[j], map.getOrDefault(a[j], 0)+1);}}++cnt;}}for(Map.Entry entry :map.entrySet()){if(!set.contains(entry.getKey())&&entry.getValue()==cnt)++sum;}if(sum==0){System.out.print(n-set.size());}elseSystem.out.println(sum);sc.close();}BufferedReader in = new BufferedReader(new InputStreamReader(System.in));StringTokenizer tok;String next() {while (tok == null || !tok.hasMoreTokens())try {tok = new StringTokenizer(in.readLine());} catch (IOException e) {e.printStackTrace();}return tok.nextToken();}int nextInt() { return Integer.parseInt(next()); }char nextChar() { return next().charAt(0); }
}