首页 > 试题广场 >

栗酱的文明2

[编程题]栗酱的文明2
  • 热度指数：73 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 128M，其他语言256M
  • 算法知识视频讲解
        “伟大的勇栗兔栽栗女王，所有栗子看到您都不寒而栗，但也非常尊重您。您骑着威风凛凛的小白兔，带领栗子们奋勇前行。伟大史诗告诉我们，烈兔勇栗从大草原飞奔出来，
冲在每场战争的前线——无论您在哪里，他们都能找到您。骑小白兔飞驰吧，凶猛的女王，但愿您有真正的朋友和软弱的敌人。”
今天，冰雪聪明的栗酱终于玩到了她梦寐很久的文明游戏。
不过作为一个萌新，兔头獐脑的栗酱自然不愿意第一次玩就遇到一个尴尬的结局，于是希望通过你来寻找一个完美结局。

已知游戏结束前场上有n个国家，第i个国家有ai块土地，任意2个国家若是想建立外交关系，则需要互相在对方的一块土地上建立一个大使馆。
一块土地只能建立一个大使馆，若一个国家和其他国家存在外交关系，则需要征用一块己方土地作为备用大使馆。
完美结局的定义是：找到最多数量的国家，使他们相互之间存在外交关系。

输入描述:
第一行一个数T，表示有T组数据。
对于每组数据，第一行输入一个数n，表示国家的数量，接下来一行输入n个数，a1,a2,…,an,其中ai表示第i个国家拥有的土地数量。每两个相邻的数之间用空格隔开。


输出描述:
对于每一个询问，输出一个数，即完美结局下，相互建立外交关系的国家数量。
示例1

输入

2
5
2 2 2 2 2
10
8 6 5 9 2 7 10 3 3 9

输出

2
6

说明

对于第一个样例：
最多只能找到2个国家，使他们互相建立外交关系。
对于第二个样例：
第1,2,4,6,7,10个国家间可互相建立外交关系，最多数量为6。

备注:
T≤10
1≤n≤1000
1≤ai≤n

算法知识视频讲解
开通博客
头像 牛奶烧仙草
发表于 2021-11-16 18:34:41
一个国家如果要与n国家建立外交关系，就需要n块土地建立大使馆，除去大使馆所占的土地自己必须至少有一块土地自己用。 排序从大到小，当大使馆所占用土地等于自身有的土地减去至少一块保留土地，即结束 ```#include<stdio.h> #include<stdlib.h> in 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 AmaZhao
发表于 2025-09-25 13:08:42
本题中试图通过排序后从后往前遍历来找到最大的国家数量k，但条件判断有误。正确的做法是找到最大的k，使得至少有k个国家的土地数量至少为k。这可以通过对土地数量排序后，从k=1到n依次检查第k大的土地数量是否至少为k来实现。 原代码漏洞分析： 1 条件判断错误：原代码使用A[j] > n - j 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 god_lip
发表于 2022-06-15 11:49:04
这个题目就是简单的找规律 可以先用sort给他排序一下，然后你发现从大到小，那个所剩余的土地，是需要大于，你可以建交的国家的 数量的，答案就出来了 #include<bits/stdc++.h> using namespace std; const int MAX=100010; int 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

枚举 排序
难度：
0条回答 2060浏览

热门推荐

通过挑战的用户

相关试题

栗酱的文明2

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号