首页 > 试题广场 >

预知

[编程题]预知

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

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

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

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

输入描述:

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

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

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

输出描述:

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

示例1

输入

输出

0
-1
3

说明

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

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

算法知识视频讲解

Gooby114514

发表于 2024-12-30 11:00:20

D 预知本题使用到了鸽巢原理（抽屉原理）的思想。首先考虑的情况，由于总卡牌数，故这是必败的。当时，看样例也能发现分为几种情况：全是时，说明随便翻两张都必胜，所以只有一个时，例如这种情况，很多同学以为要预知张，其实只要张就够了，因为预知出来的两张都一样的话展开全文

牛客856751393号

发表于 2025-03-08 21:32:20

while True: try: T = int(input()) for _ in range(T): n = int(input()) a = list(map(int, input().split())) 展开全文

郁闷的王老五风度翩翩

发表于 2025-02-28 23:27:14

n =int(input()) result = [] for i in range(n): types = int(input()) cards = list(map(int,input().split())) maxs = max(card for card in car 展开全文

覃亦语

发表于 2025-03-18 20:05:22

''' 如果牌的种类大于1，且只有1种牌的数量大于1张：我们需要预知足够多的卡牌，使得剩下未预知的卡牌中，每种的数量最多为1。这样剩下的牌无论怎么选两张都不会相同，此时玩家只需要从剩下的牌里翻牌。如果牌的种类大于1，且每种牌的数量都大于1张：需要预知数量最多的种类的所有牌，然后玩家从已预知的牌里抽展开全文

在写文章的小白菜很犯困

发表于 2025-05-23 17:39:02

思路：从全集S中随机选取p个元素后，形成了两个集合。S1：选取的已知的p个元素S2：剩下未知的元素如何根据S1和S2做出必胜的判断——即一定不会抽到两个相同元素？1、要求S1的元素包含至少两种不同的类或者某个类的全部元素。根据鸽巢原理可得p1=max(占比最大的类的元素的个数）2、要求S2包含每个类展开全文

Simon233

发表于 2025-05-21 14:38:06

题目可以理解为只知道卡牌的种类数与对应数量，在最倒霉的情况下提前知道几张牌能获胜（这个随机和至少有点歧义，倒霉应该好理解一点）一共三种情况：1.只有一种牌：必输2.除了最多的牌，其它牌数量均为1：预知（最多的牌数量-1）张最多的牌，然后翻开其余任意两张牌即可（此时所有牌的数量都为1）3.其余一般情况展开全文

番禺小韭菜

发表于 2025-03-04 23:00:59

#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 10; int a[N]; void solve() { int n; cin >> n; for (int i = 1; 展开全文

Serein_Addison

发表于 2025-06-10 22:16:39

/*三种情况：第一种是只有一种卡牌，输出不可能即可。第二种是只有一种卡牌个数为a不为1，其他均为以，这时只需要保证让剩下的卡牌均为1即可，即输出a-1即可。第三种是有多种卡牌个数不为1，这是只要保证最多的卡牌全部找出来即可。 */ #include <stdio.h> int ma 展开全文

魂祈梦

发表于 2025-10-16 13:00:35

const rl = require("readline").createInterface({ input: process.stdin }); var iter = rl[Symbol.asyncIterator](); const readline = async () = 展开全文

学习小生

发表于 2025-08-28 13:31:20

T = int(input()) for t in range(T): n = int(input()) arr = list(map(int,input().split())) arr1 = arr.copy() arr1.remove(max(arr1)) 展开全文

问题信息

数论

难度：

18条回答 104收藏 338浏览

预知

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

相关试题