首页 > 试题广场 >

预知

[编程题]预知

热度指数：4255 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 牌桌上有 $n$ 种不同的卡牌，第 $i$ 种卡牌有 $a_i$ 张。初始时，所有的卡牌均背面朝上，但不知道其确切的种类。你有两次翻牌机会，翻牌后，如果两张卡牌种类一致，那你就输了。两次翻牌同时进行（不存在根据翻开的第一张牌更改策略的情况）。

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

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

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数  代表卡牌种类数。
第二行输入  个整数  代表每种卡牌数量。

除此之外，保证每一组测试数据的卡牌总数之和不小于  ；单个测试文件的  之和不超过  。

输出描述:

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

示例1

输入

输出

0
-1
3

说明

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

对于第二组测试数据，由于卡牌种类唯一，不管怎么翻都会输。

算法知识视频讲解

牛客161651952号

这题有歧义，正常除了必输和必赢，剩下的情况为了保证必胜都需要预测到剩两张。而用例却不是这个意思，用例是相当于k = 数量最多的那种卡牌的数量。当其余种类都为1个，k--；
示例给的还极具迷惑性，2种，2和3，当然是3。但是如果是2种，3和3呢，你预测3张怎么可能必胜。

你如果说题干说最少，3张刚好都是一种，那示例中2种，2和3，最少预测数应该是2

发表于 2025-05-26 19:42:57 回复(2)

Python3

忧伤的双曲线

只需要知道除了最大数外其余数是否均为1即可，是则输出max-1，不是则输出max

T = int(input())

for i in range(T):

n = int(input())

a = list(map(int,input().split()))

if n==1:

print(-1)

else:

if sum(a)==max(a)+n-1:

print(max(a)-1)

else:

print(max(a))

发表于 2025-03-21 11:30:41 回复(0)

Python3

def__我爱上班__

T = int(input())
for i in range(T):
    n = int(input())
    p = list(map(int,input().split()))
    if n==1:
        print(-1)
    else:
        if sum(p)==max(p)+n-1:#“除最大堆外，所有其他卡牌数量均为 1”
            print(max(p)-1)#随机预知k张;①预知的选一张，剩余的选一张。②预知的里面选两种
        else:
            print(max(p))#①预知的选一张，剩余的选一张。②预知的里面选两种，k张牌中必然包含两种（对应②），或者只为数量最多的牌（对应①）。

发表于 2025-06-08 21:57:08 回复(0)

C++

nothing5

这个题开始没有说已知每种卡牌数量；于是我根据案例给出第一种思路：

/**

* 先将卡牌数量存放在arr数组里，对其从大到小排序

* 判断每种卡牌数量有没有超过1的，都为1，输出0

* 判断第二个的数量是否为1，若为1，且只有两种卡牌（arr.size() == 2），输出第一个的大小-1

根据上面思路只能通过两个；在比较其他案例，需要去掉arr.size() == 2;因为卡牌数量存在只有第一个不为1，其他都为1的情况；一下是我的整体解决：

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

void solt() {

int n;//代表种类

cin >> n;

vector<int> arr;

int n_cpy = n;

while (n--) {

int num;

cin >> num;

arr.push_back(num);//将每种卡牌数量放入到arr数组中

}

if (n_cpy == 1) {

cout << "-1" << endl;

return;

}

/**

* 判断每种卡牌数量有没有超过1的，都为1，输出0

* 判断第二个的数量是否为1，若为1，输出第一个的大小-1

sort(arr.begin(), arr.end(), [](auto it1, auto it2){

return it1 > it2;

});

//每种卡牌数量为1

if (arr[0] == 1) {

cout << "0" << endl;

}else if (arr[1] == 1) {

cout << arr[0] - 1 << endl;

}else {

cout << arr[0] << endl;

}

/**

* 评论区的解法

// int count = 0;

// for (int i : arr) {

// if ( 1 == i ) {

// count++;

// }

// int it = *max_element(arr.begin(), arr.end());

// if (it == 1) { //只有一种卡牌

// cout << "0" << endl;

// } else if (count == arr.size() -1) {

// cout << it- 1 << endl;

// }else {

// cout << it << endl;

// }

}

int main() {

ios::sync_with_stdio(false);

cin.tie(nullptr);

int T;

cin >> T;

while (T--) {

solt();

}

return 0;

}

发表于 2025-10-21 09:35:49 回复(0)

牛客916838684号

为什么这么多题我连题目都看不懂

发表于 2025-09-27 12:13:46 回复(0)

C++

牛客230982145号

写法不难，但是很难读懂理解（并非是本人一开始想到的，也是参考他人答案所得的理解）

简单的来说，如果就1种卡牌，结果自然是-1，没法赢。

如果是2种及以上的卡牌，比如说有4种卡牌，一共20张，2 4 6 8

A:要么，你预测16张，剩下的4张是不同的4种，随便拿就能赢

B:要么，你把其中牌数最多的那一种全预测出来，你拿这个数量最多的一张，再随便拿一张别的就能赢

然后你就比较A和B的大小，谁小谁就是结果

-----------------------------------------------------------------------------------------

虽然题目可以按以上的简单写法能通过，但是本题就我个人理解，如果预测两张卡牌正好是不同的，那我直接选这两张不就直接赢了，从题目来看，玩家即不知道卡牌的种类，也不知道具体卡牌种类的张数，2 4 6 8，又凭什么预测8张就能确信是必赢了。

欢迎各位在评论区讨论

编辑于 2025-09-14 19:30:29 回复(0)

Python 3

学习小生

T = int(input())
for t in range(T):
    n = int(input())
    arr = list(map(int,input().split()))
    arr1 = arr.copy()
    arr1.remove(max(arr1))
    if len(arr1) == 0:
        print(-1)
    else:
        if max(arr1) == 1:
            print(max(arr) - 1)
        else:
            print(max(arr))

发表于 2025-08-28 13:32:10 回复(0)

在思考的熊猫很慢热

#include <stdio.h>

#define MAX_SIZE 1000

int main() {
int T; // 测试用例的数量
scanf("%d", &T); // 读取测试用例数量

// 处理每个测试用例
while (T--) {
int n; // 当前测试用例的数字个数
scanf("%d", &n); // 读取数字个数
int vec[MAX_SIZE]; // 存储数字的固定大小数组
int m; // 临时变量，用于读取每个数字
int n_cpy = n; // 保存n的副本，因为后面n会递减

// 读取所有数字并存入数组
for (int i = 0; i < n; i++) {
scanf("%d", &m); // 读取一个数字
vec[i] = m; // 存入数组
}

// 特殊情况处理：如果只有一个数字
if (n_cpy == 1) {
printf("-1\n"); // 直接输出-1
}
else {
// 统计数字1的个数
int one_number = 0;
for (int i = 0; i < n_cpy; i++) {
if (1 == vec[i]) {
one_number++; // 遇到1就计数
}
}

// 情况1：所有数字都是1
if (one_number == n_cpy) {
printf("0\n"); // 输出0
}
// 情况2：只有一个数字不是1
else if (one_number == n_cpy - 1) {
// 找出最大的数字
int max = vec[0];
for (int i = 1; i < n_cpy; i++) {
if (vec[i] > max) {
max = vec[i]; // 更新最大值
}
}
printf("%d\n", max - 1); // 输出最大值减1
}
// 情况3：其他情况
else {
// 找出最大的数字
int max = vec[0];
for (int i = 1; i < n_cpy; i++) {
if (vec[i] > max) {
max = vec[i]; // 更新最大值
}
}
printf("%d\n", max); // 直接输出最大值
}
}
}
return 0; // 程序结束
}

发表于 2025-07-20 20:03:05 回复(0)

Java

金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)

C++

爱吃肉的咸鱼在春招

#include <algorithm>
#include <iostream>
#include <mutex>
#include <set>
#include <vector>
using namespace std;

int main() {

    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;
        vector<int> vec;
        int m;
        int n_cpy = n;
        while (n--) {
            cin >> m;
            vec.push_back(m);
        }

        if ( n_cpy == 1 ) {
            cout << -1 << endl;
        } else {
            int one_number = 0;
            for (int i : vec) {
                if ( 1 == i ) {
                    one_number++;
                }
            }

            if ( one_number == vec.size() ) {
                cout << 0 << endl;
            } else if( one_number == vec.size() - 1 ) {
                cout << *max_element(vec.begin(), vec.end()) - 1 << endl;
            }else {
                cout << *max_element(vec.begin(), vec.end()) << endl;
            }

        }

    }

}
// 64 位输出请用 printf("%lld")

发表于 2025-05-08 01:13:13 回复(0)

Goldminer

10
2
2 8
2
7 3
4
12 1 3 4
2
7 3
1
5
2
3 7
1
5
4
1 1 3 15
1
5
1
5
这个第一个我直接预测单侧最少张不可以吗？为什么通过的预期结果是8张

发表于 2025-04-22 21:40:02 回复(0)

emdnauoy

n = int(input())

def win(n,ls):

if n == 1:

return -1

elif n>1 and all(item ==1 for item in ls):

return 0

else:

return max(ls)

while True:

try:

n = int(input())

ls = list(map(int,input().split()))

res = win(n,ls)

print(res)

except:

break

发表于 2025-04-20 10:39:44 回复(0)

C++

牛客700324568号

#include <iostream>

#include<vector>

using namespace std;

int main() {

int T;cin>>T;

while(T--)

{

int n;cin>>n;

// vector<int> vec;

int flag=0;

int max=0;

//预知--保证：最坏情况的足够预知数量

if(n==1){int a=0;cin>>a;cout<<"-1"<<endl;continue;}

else//>2

{

for(int i=0;i<n;i++)

{

int a;cin>>a;

if(a!=1)flag++;

max=max<a?a:max;

}

if(flag==0)cout<<"0"<<endl;

else if(flag==1)cout<<max-1<<endl;

else cout<<max<<endl;

}

// 64 位输出请用 printf("%lld")

发表于 2025-04-11 12:11:39 回复(0)

C++

想堆雪人的丘比特在冲浪

#include <iostream>

#include <numeric>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

int t;

cin >> t;

while(t--){

int n;

cin >> n;

vector<int> resVec;

for(int i = 0; i < n ; i++)

{ int temp;

cin >> temp;

resVec.push_back(temp) ;

}

int sum = accumulate(resVec.begin(), resVec.end(), 0);

int maxEle = *max_element(resVec.begin(), resVec.end());

if(n == 1)

{

cout << -1 << endl;

} else if(maxEle == 1)

{

cout << 0 << endl;

} else{

cout << min((sum - n), maxEle) << endl;

}

// 64 位输出请用 printf("%lld")
为什么我这样部分用例不通过，找不出问题了，求大佬

发表于 2025-04-02 13:43:02 回复(0)

pigx

这题我都读不懂

发表于 2025-03-28 16:50:19 回复(0)

Java

牛客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)

Sen🍓🍀

题干里

【你不喜欢运气游戏，所以你可以通过手段随机预知 kk 张卡牌后再进行游玩。
然而，预知很累！你想要知道，你至少需要预知多少张卡牌，才能保证你不会输。】

，要求的是最优解，见题解思路即可

发表于 2025-03-13 20:22:45 回复(0)

牛客67167038号

不太理解这样为什么是错的：

const rl = require("readline").createInterface({ input: process.stdin });
const iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
    const data = [];
    while ((line = await readline())) {
        data.push(line);
    }
    const count = Number(data.shift());
    for (let i = 0; i < count; i++) {
        const total = Number(data.shift());
        const arr = data
            .shift()
            .split(" ")
            .map((item) => Number(item));
        if (total === 1) {
            console.log(-1);
        } else {
            const sum = arr.reduce((pre, cur) => cur + pre, 0);
            console.log(sum - total);
        }
    }
})();

发表于 2025-03-05 17:27:53 回复(0)

提交观点

问题信息

数论

难度：

18条回答 104收藏 342浏览

预知

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题