NC14669 栗酱的文明2——牛客

题目链接：https://ac.nowcoder.com/acm/problem/14669

来源：牛客网

题目描述

“伟大的勇栗兔栽栗女王，所有栗子看到您都不寒而栗，但也非常尊重您。您骑着威风凛凛的小白兔，带领栗子们奋勇前行。伟大史诗告诉我们，烈兔勇栗从大草原飞奔出来，
冲在每场战争的前线——无论您在哪里，他们都能找到您。骑小白兔飞驰吧，凶猛的女王，但愿您有真正的朋友和软弱的敌人。”
今天，冰雪聪明的栗酱终于玩到了她梦寐很久的文明游戏。
不过作为一个萌新，兔头獐脑的栗酱自然不愿意第一次玩就遇到一个尴尬的结局，于是希望通过你来寻找一个完美结局。

已知游戏结束前场上有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

思路

• 题意理解：n个国家相互建立外交关系的意思是这n个国家内部任意两个国家都存在外交关系，外交数量为n的组合数c_nⁿ，相当于搞小团体。
• 思路：土地数量越多，则建立外交的可能性越大，因此对国家数量降序排序，则第i个国家要想搞小团体（i≥1），就要和前面i-1个国家建立外交（前面i-1个国家土地数量都大于第i个国家，所以不用考虑），则a[i]≥i为条件，排序后满足该条件的国家之间可以相互建立外交关系。
• bits：bits/stdc++.h该头文件内包含大量库的头文件，vs中使用需要自己创建该文件，缺点是bits/stdc++.h不可移植且增加编译时间增加代码大小，优点是减少写代码的工作量。

AC代码

#include<bits/stdc++.h>

using namespace std;
//降序排列
int cmp(int a, int b) {
    return a > b;
}
int t = 0;//t组数据
int n = 0;//n个国家
int a[1001];//国家的土地数量，因为备注里tidao1≤n≤1000，故可以固定大小
int res = 0;//结果

int main() { 
    cin >> t;
    while(t--) {
        cin >> n;
        for(int i = 1; i <= n; i++) {
            cin >> a[i];//传入数据，n个国家对应的土地数量存入a[i]
        }
        //a代表内存地址，从第一个元素到第n个元素按cmp排序
        sort(a + 1, a + 1 + n, cmp);
        for(int i = 1; i <= n; i++) {
            if(a[i] < i) {
            //直接记录从左往右第一个不符合的国家的前一个国家，也就是记录排序后符合完美外交的国家列表的右边界
                res = i - 1;
                break;
            }     
        }
        cout<<res<<endl;
    }
    return 0;
}