循环结构习题-1026栗酱的文明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

解题思路：
因为要求最大值，所以要尽量让土地多的国家相互建立外交关系

所以程序的框架就是先以降序排序，再循环判断这个国家能否与前面的国家建交。

总结一下就是，给出每个点最多可以和多少个点相连，让你找出能构成完全图的最多的点的个数。如果想要组成完全图，那每个点之间都要有连线，也就是说每个点所能连的线应该大于等于完全图中点的个数。我们只要将点的连线个数从大到小之后排序再找一遍即可。

代码：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010
int a[MAXN];
bool cmp(int x , int y)
{
    return x >= y;
}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        int res = 0;
        for(int i = 1 ; i <= n ; i++)
        {
            cin >> a[i];
        }
        sort(a+1,a+n+1,cmp);
        for(int i = 1 ; i <= n ; i++)
        {
            if(a[i] < i)
                break;
            res = i;
        }
        cout << res << endl;
    }
    return 0;
 }