首页 > 试题广场 >

预知

[编程题]预知

热度指数：5510 时间限制：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)

C++

牛客230982145号

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

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

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

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

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

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

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

为什么答案是这两者取其中最小的，理想情况自然是抽两张，两张不同就是结果，但是我们无法保证预测的牌型结果，所以就会产生以上两种情况

情况A：

就纯点背，2 4 6 8，20张牌，抽了16张了，还是没把某一个牌型抽空，但是没有预测的牌型都是一张了，随便拿两张就赢了

情况B：

连着抽了8张了，都是8张的那个牌型，但是，我已经把这个牌型抽空了，我从预测的这里面抽一张，从没预测的12张里面随便抽一张，就赢了

这时候可能有疑问，我抽2张，把2张的牌型抽空了，不也是情况B吗，为什么情况B是要抽8张，因为你无法保证你抽的牌型，就是点背，你就是抽了8次才抽空他，所以至少抽8次

这时候，比较情况A B，取最小值即是答案

编辑于 2026-04-14 09:50:01 回复(2)

牛客916838684号

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

发表于 2025-09-27 12:13:46 回复(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)

陌上谁家年少

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

import java.util.Scanner;

// 注意类名必须为 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();

long sum = 0;

List<Integer> resultList = new ArrayList<>();

for (int i =0;i < t;i++) {

// 卡牌种类数

int n = in.nextInt();

sum += n;

if (sum > Math.pow(10,5)*2) {

System.out.println("输入不规范");

break;

}

// 每种卡牌数量

List<Integer> numList = new ArrayList<>();

long cardSum = 0;

for (int j =0;j < n;j++) {

int num = in.nextInt();

numList.add(num);

cardSum+=num;

}

if (cardSum < 2) {

System.out.println("输入不规范2");

break;

}

// 种类单一，必输

if (n == 1) {

resultList.add(-1);

// System.out.println(-1);

continue;

}

// 每种卡牌数量都为1，必赢，翻开即可

int max = Collections.max(numList);

if (max == 1) {

resultList.add(0);

// System.out.println(0);

continue;

}

// 保守情况下预知某类卡牌数量最多的，就可以保证不会输

// 如果少预知1张某类卡牌数量最多的后，每种卡牌数量都为1，则没必要把某类卡牌数量最多的全预知了

int idx = numList.indexOf(max);

numList.set(idx, 1);

int max2 = Collections.max(numList);

if (max2 == 1) {

resultList.add(max - 1);

// System.out.println(max - 1);

} else {

resultList.add(max);

// System.out.println(max);

}

for (Integer result:resultList) {

System.out.println(result);

}

发表于 2026-04-27 16:01:36 回复(0)

C++

Xue1_

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    cin >> n;
    
    long long max_a = 0;
    int count_ge_2 = 0; // 记录数量大于等于 2 的卡牌种类数
    
    for (int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        if (a >= 2) {
            count_ge_2++;
        }
        max_a = max(max_a, a);
    }
    
    // 只有一种卡牌，必死无疑
    if (n == 1) {
        cout << -1 << "\n";
        return;
    }
    
    // 根据上面的推导进行判断
    if (count_ge_2 == 0) {
        // 没有任何重复的牌，闭着眼翻都能赢
        cout << 0 << "\n";
    } else if (count_ge_2 == 1) {
        // 只有一种牌有重复，留一张在暗牌里当内鬼，暗牌堆就全是不重复的牌了
        cout << max_a - 1 << "\n";
    } else {
        // 有多种牌存在重复，必须把最多的那种牌全看光
        cout << max_a << "\n";
    }
}

int main() {
    // 算法竞赛起手式：解除输入输出的绑定，提升速度
  
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

发表于 2026-04-21 01:09:17 回复(0)

猫猫猫1

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        int Max = 0, count = 0;
        cin >> n;
        vector<long long> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] > Max) {
                Max = a[i];
            }
            if (a[i] > 1) {
                count++;
            }
        }
        if (n == 1) {
            cout << -1 << endl;
        } else if (count == 0) {
            cout << 0 << endl;
        } else if (count == 1) {
            cout << Max - 1 << endl;
        } else {
            cout << Max << endl;
        }
    }
    return 0;
}

发表于 2026-04-16 18:57:51 回复(0)

C++

爱看剧的花生米躺平又起来了

#include <iostream>

using namespace std;

int main() {

int T;

cin >> T;

while (T > 0) {

int n;

cin >> n;

int max = 0;//记录最大的数

int count = 0;//记录大于1的数的个数

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

int k;

cin >> k;

if (k > 1)count++;

max = max > k ? max : k;

}

if (n < 2) {

cout << -1 << endl;//只有一种卡牌，必输

}

//大于2的卡牌超过一张，运气最差的情况下全预知卡牌数最多的卡牌

//取卡牌数最多的卡牌与其他任意卡牌可保证必胜

else if (count > 1)cout << max << endl;

//只有一张卡牌卡牌数大于2，运气最差的情况下预知到max-1张卡牌数最多的卡牌，剩下的卡牌随意选取两张可保证必胜（余下的所有卡牌均只有一张）

else cout << max - 1 << endl;

T--;

}

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

发表于 2026-02-13 18:34:27 回复(0)

Python3

Chinry

T=int(input())
for i in range(T):
    n=int(input())
    a=list(map(int,input().split()))
    if n==1:
        print('-1')
    else:
        result=sum(a)-n if sum(a)-n<=max(a) else max(a)
        print(result)

发表于 2025-12-25 20:18:01 回复(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)

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)

提交观点

问题信息

数论

难度：

23条回答 124收藏 812浏览

预知

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题