第十三届蓝桥杯JavaB组国赛H题——小球称重 (AC)
目录
- 1.小球称重
- 1.问题描述
- 2.输入格式
- 3.输出格式
- 4.输入样例
- 5.样例输出
- 6.样例说明
- 7.数据范围
- 8.原题链接
- 2.解题思路
- 3.Ac_code
1.小球称重
1.问题描述
小蓝有 NNN 个小球, 编号 1 至 NNN 。其中 N−1N-1N−1 是正品, 重量相同; 有 1 个是 次品, 重量比正品轻。
为了找出次品, 小蓝已经用天平进行了 MMM 次称重, 并且记录下来每次两边 放的小球编号, 和称重结果。
请你根据记录, 判断还剩下几个小球有次品的嫌疑。
2.输入格式
第一行包含 2 个整数 NNN 和 MMM 。
以下包含 MMM 次称重记录, 每个记录占 4 行。
第一行是一个整数 KKK, 表示天平两边各放了 KKK 个小球。
第二行包含 KKK 个整数, 代表放在天平左边的小球编号。
第三行包含 KKK 个整数, 代表放在天平右边的小球编号。
第四行是一个字符, 为 ’ > ', ‘<’, ’ = ‘之一。’ > ’ 代表左边比右边重, ‘<’ 代表右边比左边重
在一次称重中保证每个小球最多出现 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,61,2,3<4,5,61,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 能判断出 333 不可能是次品。
所以只剩下 1,2{1,2}1,2 可能是次品。
7.数据范围
1≤N≤109,1≤M≤1051≤N≤10^9 ,1≤M≤10^51≤N≤109,1≤M≤105 , 参与 M 次称重的小球总数≤106\leq 10^{6}≤106
8.原题链接
小球称重
2.解题思路
小球的数量总共有1e91e91e9个,参与称重的小球却只有1e61e61e6个,所以我们从参与称重的小球入手来解决问题。设 nnn 为小球的数量,xxx 为参与称重的小球数量,我们先将称重的情况分为两类,
一类是称重情况为>
或<
的,出现这种情况说明我们可以将次品小球锁定在一堆小球内。我们使用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();}
}
.
相关文章:
第十三届蓝桥杯JavaB组国赛H题——小球称重 (AC)
目录1.小球称重1.问题描述2.输入格式3.输出格式4.输入样例5.样例输出6.样例说明7.数据范围8.原题链接2.解题思路3.Ac_code1.小球称重 1.问题描述 小蓝有 NNN 个小球, 编号 1 至 NNN 。其中 N−1N-1N−1 是正品, 重量相同; 有 1 个是 次品, 重量比正品轻。 为了找出次品, 小蓝…...