首页 > 试题广场 >

公平竞争

[编程题]公平竞争

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

牛牛新开发了一款卡牌游戏，在这款游戏中，系统随机给出 $\mathit n$ 张卡牌，每张卡牌都有战斗力和独特的技能，每张卡牌只能被选择一次，每位玩家必须手持其中的两张卡牌进入游戏。

为了保证游戏的公平性，牛牛规定，只有当每位玩家手中的两张卡牌战斗力之和相同时，才能认为这个对局是公平的。

但是牛牛发现，如果让玩家自行选择卡牌，总是会出现战斗力一边倒的局面，所以，他想请你写一个程序，由系统来完成随机分配卡牌的任务。

那么，在已知 $\mathit n$ 张卡牌各自战斗力，且保证对局公平的情况下，此局游戏最多可以允许多少位玩家参与战斗？

输入描述:

本题为多组测试数据，第一行输入一个正整数 ，代表测试数据组数。

对于每组测试数据，第一行输入一个正整数 ，代表卡牌数量。
第二行输入  个正整数 ，依次代表每张卡牌的战斗力。

输出描述:

对于每组测试数据，一行输出一个整数代表最多可以有多少位玩家参与战斗。特殊的，由于一场对局至少需要两名玩家，所以，若在保证对局公平的基础上，不能支持至少两名玩家参与对局，那么，只需要输出  代表该对局作废。

示例1

输入

输出

-1
2

说明

第一个测试数据中，只有三张卡牌，由于一个玩家就需要手持两张卡牌，所以无论如何都不能支持至少两名玩家进行游戏。
第二个测试数据中，第一张卡牌和第四张卡牌的战斗力之和等于第二张卡牌和第三张卡牌的战斗力之和，可以让最多两名玩家同时进行游戏。

算法知识视频讲解

Zero′

根据题意得出我们要任选两个数且不能重复选择，统计他们和的数量求出最大值。

那么我们可以得到和是固定的，且根据数据范围不会超过200，那么我们就可以枚举他的和，再枚举某一个数，求出和为k的数量。

最后求出最大值就可以了。

#include<iostream>
#include<cstring>
using namespace std;
const int N = 210;
int f[N];
int t, n;
int main() {
    cin >> t;
    while(t--) {
        memset(f, 0, sizeof f);
        cin >> n;
        for(int i=0;i<n;i++) {
            int x;
            cin >> x;
            f[x]++;
        }
        int ans = 0;
        for(int i=2;i<=200;i++) {
            int sum = 0;
            for(int j=1;j<=i/2;j++) {
                if(!f[j] || !f[i-j]) continue;
                if(j == i - j) sum += f[j] / 2;
                else sum += min(f[i-j], f[j]);
            }
            ans = max(sum, ans);
        }
        if(ans <= 1) cout << -1;
        else cout << ans;
        cout << endl;
    }
}

发表于 2022-02-22 15:24:36 回复(0)