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

你的名字 2023-09-28 23:16 57阅读 0赞

#### 目录 ####

*  1.小球称重
 *   *  1.问题描述
     *  2.输入格式
     *  3.输出格式
     *  4.输入样例
     *  5.样例输出
     *  6.样例说明
     *  7.数据范围
     *  8.原题链接
 *  2.解题思路
 *  3.Ac\_code

## 1.小球称重 ##

### 1.问题描述 ###

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

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

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

### 2.输入格式 ###

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

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

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

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

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

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

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

### 3.输出格式 ###

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

### 4.输入样例 ###

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

### 5.样例输出 ###

### 6.样例说明 ###

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

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

所以只剩下  1 , 2 \{1,2\} 1,2 可能是次品。

### 7.数据范围 ###

1 ≤ N ≤ 1 0 9 , 1 ≤ M ≤ 1 0 5 1≤N≤10^9 ,1≤M≤10^5 1≤N≤109,1≤M≤105 , 参与 M 次称重的小球总数 ≤ 1 0 6 \\leq 10^\{6\} ≤106

### 8.原题链接 ###

[小球称重][Link 1]

## 2.解题思路 ##

小球的数量总共有 1 e 9 1e9 1e9个，参与称重的小球却只有 1 e 6 1e6 1e6个，所以我们从参与称重的小球入手来解决问题。设  n n n 为小球的数量， x x 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();
        }
    }

[Link 1]: https://www.lanqiao.cn/problems/2235/learning/