首页 > 试题广场 >

预知

[编程题]预知
  • 热度指数：4253 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}牌桌上有 n 种不同的卡牌，第 i 种卡牌有 a_i 张。初始时，所有的卡牌均背面朝上，但不知道其确切的种类。你有两次翻牌机会，翻牌后，如果两张卡牌种类一致，那你就输了。两次翻牌同时进行（不存在根据翻开的第一张牌更改策略的情况）。

\hspace{15pt}你不喜欢运气游戏，所以你可以通过手段随机预知 k 张卡牌后再进行游玩。

\hspace{15pt}然而，预知很累！你想要知道，你至少需要预知多少张卡牌，才能保证你不会输。

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\left(1\leqq T\leqq 2 \times 10^5\right) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}第一行输入一个整数 n\left(1\leqq n\leqq 2 \times 10^5\right) 代表卡牌种类数。
\hspace{15pt}第二行输入 n 个整数 a_1, a_2, \dots, a_n\left(1\leqq a_i\leqq 10^9\right) 代表每种卡牌数量。

\hspace{15pt}除此之外，保证每一组测试数据的卡牌总数之和不小于 2 ；单个测试文件的 n 之和不超过 2 \times 10^5 。


输出描述:
\hspace{15pt}对于每一组测试数据，如果没有必胜策略，直接输出 -1 ；否则，在单独的一行上输出一个整数，代表你至少需要预知多少张卡牌，才能保证你不会输。
示例1

输入

3
2
1 1
1
10
2
2 3

输出

0
-1
3

说明

\hspace{15pt}对于第一组测试数据，只有两张卡牌，且各不相同，直接翻开即可。

\hspace{15pt}对于第二组测试数据，由于卡牌种类唯一，不管怎么翻都会输。
算法知识视频讲解
添加回答
Java
金Main头像 金Main
主要是对数组中只有一个数不是1，其他全为1的场景做判断，这个要比最大值少一个。 
import java.util.Scanner;
import java.util.Arrays;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int T = in.nextInt();
            in.nextLine();
            for(int i = 0;i < T;i++){
                int n = in.nextInt();
                in.nextLine();
                int[] arr = new int[n];
                for(int j = 0;j < n;j++){
                    arr[j] = in.nextInt();
                }
                in.nextLine();
                if(n == 1){
                    System.out.println("-1");
                }else{
                    int tmp = 0;
                    for(int k = 0;k < arr.length;k++){
                        if(arr[k] == 1){
                            tmp++;
                        }
                    }
                    if(tmp == arr.length){
                        System.out.println("0");
                    }else{
                        Arrays.sort(arr);
                        int num = 0;
                        for(int l = 0;l < arr.length;l++){
                            if(arr[l] == 1){
                                num++;
                            }
                        }
                        if(num == arr.length - 1){
                            System.out.println(arr[arr.length - 1] - 1);
                        }else{
                            System.out.println(arr[arr.length - 1]);
                        }
                    }
                }
            }
        }
        in.close();
    }
}


发表于 2025-07-07 20:44:14 回复(0)
Java
牛客430757235号头像 牛客430757235号
//源代码如下
/*
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();
        in.nextLine();
        for (int i = 0; i < n; i++) {
            int q = in.nextInt();
            in.nextLine();
            String[] a = new String[q];
            a = in.nextLine().split("\\s+");//存放本次不同种类卡牌数量
            if (q == 1) {
                System.out.println(-1);
            } else {
                int w = Integer.MIN_VALUE;
                int num = 0;
                int tol1 = 0;
                boolean yes = false;
                for (int j = 0; j < q; j++) {
                    if(Integer.parseInt(a[j])==1){
                        tol1++;
                    }
                    num = num + Integer.parseInt(a[j]);
                    w = Math.max(w, Integer.parseInt(a[j]));
                }
                if(tol1+1 == q){
                    yes = true;
                }
                if (w == 1) {
                    System.out.println(0);
                } else if (yes) {
                    System.out.println(num-q);
                } else {
                    System.out.println(w);
                }
            }
        }
        in.close();
    }
}
*/
/*程序逻辑是对的 但超时了  仔细分析题目可以总结发现
卡牌种类为1时 不可以  输出-1
卡牌种类大于等于2时讨论
如果每个种类卡牌数都为1时 0次可以  输出0
当至少存在一个卡牌类型且该卡牌数量为1 时 此时 输出 所有类型卡牌总数量减去卡牌类型个数  举例子卡牌类型4个  每个数量如下1 1 3 8   此时输出(1+1+3+8-4)=9
其他情况：种类卡牌数量不一样时候  输出某个种类卡牌数量最大值

*/

//以下是D老师帮我优化输入后得到的 一更改 通过啦
import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
       
        int T = Integer.parseInt(br.readLine());
       
        for (int t = 0; t < T; t++) {
            int q = Integer.parseInt(br.readLine().trim());
           
            if (q == 1) {
                bw.write("-1\n");
                br.readLine(); // 消耗剩余空行
                continue;
            }
           
            StringTokenizer st = new StringTokenizer(br.readLine());
            int sum = 0;
            int max = 0;
            int tol1 = 0;
           
            while (st.hasMoreTokens()) {
                int num = Integer.parseInt(st.nextToken());
                sum += num;
                max = Math.max(max, num);
                if (num == 1) tol1++;
            }
           
            boolean yes = (tol1 + 1 == q);
           
            if (max == 1) {
                bw.write("0\n");
            } else if (yes) {
                bw.write((sum - q) + "\n");
            } else {
                bw.write(max + "\n");
            }
        }
       
        bw.flush();
        bw.close();
        br.close();
    }
}

发表于 2025-03-16 16:38:32 回复(0)
提交观点

问题信息

数论
难度：
2条回答 339浏览

热门推荐

相关试题

预知

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号