题解 | #D 预知#

预知

https://ac.nowcoder.com/acm/contest/99458/D

D 预知

本题使用到了鸽巢原理(抽屉原理)的思想。

首先考虑 的情况,由于总卡牌数 ,故这是必败的。

时,看样例也能发现分为几种情况:

  • 全是 时,说明随便翻两张都必胜,所以
  • 只有一个 时,例如 这种情况,很多同学以为要预知 张,其实只要 张就够了,因为预知出来的两张都一样的话,说明剩下的四张就成了全 的情况,所以
  • 其他情况, ,因为我们预知 张相同的卡牌后,就知道了剩下的所有卡牌和已经知道的卡牌都是不一样的,从这两堆里各选一张即可。
#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; i <= n; i ++ ) cin >> a[i];
    if (n == 1) {
        cout << -1 << endl;
        return ;
    }
    int mx = -1;
    for (int i = 1; i <= n; i ++){
        mx = max(mx, a[i]);
    }
    if (mx == 1) cout << 0 << endl;
    else {
        int cnt = 0;
        for (int i = 1; i <= n; i ++ ) {
            if (a[i] > 1) cnt ++;
        }
        if (cnt == 1) cout << mx - 1 << endl;
        else cout << mx << endl;
    }
}

int main(){
    int T; cin >> T;
    while (T -- ) solve();
    return 0;
}
全部评论
还有一种情况,只有两种牌的时候,只需要预知min-1张就可以了,这个题没有考虑到这种情况
1 回复 分享
发布于 03-19 19:15 四川
题意不对,你不喜欢运气游戏,所以你可以通过手段随机预知 k 张卡牌后再进行游玩。然而,预知很累!你想要知道,你至少需要预知多少张卡牌,才能保证你不会输。 注意是随机预知,不是准确去预知,如果你k=min,那意思就是说你预知不是随机的,你一定能预知到最少的那类牌,实际上是随机的,只有预知k=max张牌,才能保证你把最大的那一类的牌预知完,自然知道其他牌肯定和预知牌不是同一类,这是随机预知的最差情况,其他的预知,无论如何都至少能保证预知到两类牌和一类牌(存在多个牌数一样的最多数牌类)预知完。
点赞 回复 分享
发布于 05-15 19:43 湖南
我觉得在最后一种情况里k=min且k!=0才是最少的数量,你在这个最小的类型里翻一张,再去其他牌里翻一张也肯定不会失败啊
点赞 回复 分享
发布于 05-09 02:25 湖北

相关推荐

争当牛马还争不上
码农索隆:1.把简历改哈 2.猛投,狠投 3.把基础打牢 这样你在有机会的时候,才能抓住
点赞 评论 收藏
分享
05-25 10:45
门头沟学院 Java
Frank_zhan...:没实习一个项目肯定不够,可以再做一个轮子,技术栈再补一个mq,微服务,整体再换个简历模板,暑期尽量再找一个日常实习
无实习如何秋招上岸
点赞 评论 收藏
分享
评论
6
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务