首页 > 编程学习 > 蓝桥杯2022年第十三届决赛真题-小球称重

蓝桥杯2022年第十三届决赛真题-小球称重

发布时间:2022/11/12 21:28:39

题目描述

小蓝有 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<Integer,Integer> map = new HashMap<>();
	static Map<Integer,Integer> 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<Integer> 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;i<m;i++){
			int k = sc.nextInt();
			for(int j=0;j<k;j++)
				a[j] = sc.nextInt();
			for(int j=0;j<k;j++)
				b[j] = sc.nextInt();
			String str = sc.next();
			if(str.equals("=")){
				for(int j=0;j<k;j++){
					set.add(a[j]);
					set.add(b[j]);
				}
			}else{
				if(str.equals(">")){
					for(int j=0;j<k;j++){
						set.add(a[j]);
						map.put(b[j], map.getOrDefault(b[j], 0)+1);
					}
				}else{
					for(int j=0;j<k;j++){
						set.add(b[j]);
						map.put(a[j], map.getOrDefault(a[j], 0)+1);
					}
				}
				++cnt;
			}
		}
		for(Map.Entry<Integer,Integer> entry :map.entrySet()){
			if(!set.contains(entry.getKey())&&entry.getValue()==cnt)
				++sum;
		}
		if(sum==0){
			System.out.print(n-set.size());
		}else
		System.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); }
}

Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式