第十三届蓝桥杯JavaB组国赛H题——小球称重 （AC）

1.小球称重

1.问题描述

小蓝有 $N$ 个小球, 编号 1 至 $N$ 。其中 $N-1$ 是正品, 重量相同; 有 1 个是 次品, 重量比正品轻。

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

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

2.输入格式

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

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

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

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

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

第四行是一个字符, 为 ’ > ', ‘<’, ’ = ‘之一。’ > ’ 代表左边比右边重, ‘<’ 代表右边比左边重

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

3.输出格式

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

4.输入样例

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

5.样例输出

2

6.样例说明

$1,2,3<4,5,6$ 能判断出次品在 $1,2,3$ 之中。

$3,7=8,9$ 能判断出 $3$ 不可能是次品。

所以只剩下 $1,2$ 可能是次品。

7.数据范围

$1\le N\le 10^9,1\le M\le 10^5$ , 参与 M 次称重的小球总数$\le 10^6$

8.原题链接

小球称重

2.解题思路

小球的数量总共有$1e9$个，参与称重的小球却只有$1e6$个，所以我们从参与称重的小球入手来解决问题。设 $n$ 为小球的数量，$x$ 为参与称重的小球数量，我们先将称重的情况分为两类，

一类是称重情况为>或<的，出现这种情况说明我们可以将次品小球锁定在一堆小球内。我们使用set1去记录有嫌疑的小球(这里指的是在上称时出现在较轻一方的小球)，使用set2去记录排除嫌疑的小球(这里指的是上称时结果为=的小球)。如果一个小球是次品小球，那么它一定都会出现在非=结果时较轻的一边，有一次没有出现它都可以排除嫌疑，所以每次判断我们都要使用一个set3去记录此次有嫌疑的小球，如果set1没有当前小球，说明它可以排除嫌疑，如果有则放入set3，最后再将set1清空后，将set3全部放入set1，这操作相当于set1和set3取交集。

另一类是称重情况为=号，在这种情况下，我们将这一趟所有的小球都放入到set2中，当然如果set1存在当前这个小球，我们要将其移除，因为它已经被洗脱嫌疑了。

最后所有判断完毕后，当set1为空时，说明判断的所有情况都是=，说明有嫌疑的小球是那些没上过称的，答案为n-set2.size()，否则答案则为set1.size()。

为什么使用set存储呢？
因为小球在称重时有可能多次上称，出现在有嫌疑的一边，set可以帮助我们去重，且在查询和删除时的效率高，比较适合我们的需求。

3.Ac_code

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] args) throws IOException {
        String[] s=br.readLine().split(" ");
        int n=Integer.parseInt(s[0]);
        int m=Integer.parseInt(s[1]);
        //s1存放当前有嫌疑的小球
        Set<Integer> s1=new HashSet<>();
        //s2存放排除嫌疑的小球
        Set<Integer> s2=new HashSet<>();
        for(int i=0;i<m;++i){
            int k=Integer.parseInt(br.readLine());
            List<Integer> a=new ArrayList<>();
            s=br.readLine().split(" ");
            for(int j=0;j<k;++j){
                int x=Integer.parseInt(s[j]);
                a.add(x);
            }
            List<Integer> b=new ArrayList<>();
            s=br.readLine().split(" ");
            for(int j=0;j<k;++j){
                int x=Integer.parseInt(s[j]);
                b.add(x);
            }
            String ss=br.readLine();
            //仅仅记录此次判断有嫌疑的小球
            Set<Integer> s3=new HashSet<>();
            if(ss.equals(">")){
                if (s1.isEmpty()) s1.addAll(b);
                else{
                    for(int g:b){
                        if (s1.contains(g)) s3.add(g);
                    }
                    s1.clear();
                    s1.addAll(s3);
                }
            } else if (ss.equals("<")){
                if (s1.isEmpty()) s1.addAll(a);
                else {
                    for(int g:a){
                        if (s1.contains(g)) s3.add(g);
                    }
                    s1.clear();
                    s1.addAll(s3);
                }
            } else{
                for(int j=0;j<k;++j){
                    s2.add(a.get(j));
                    s2.add(b.get(j));
                    s1.remove(a.get(j));
                    s1.remove(b.get(j));
                }
            }
        }
        if(s1.isEmpty()) out.println(n-s2.size());
        else out.println(s1.size());
        out.flush();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

.