【栗子的文明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

分析：

对数据从大到小排序后可以发现
例如示例第二组数据，排序后得：10 9 9 8 7 6 5 3 3 2
1.当第 i 个国家的土地数Xi = i 时，这时互相建立外交的国家数最多
再比如：5 4 4 3 2这组数据
2.当第 i 个国家的土地数Xi，对于第一种情况找不到Xi = i,那么再3之前的三个国家就是最大外交数量。

C语言代码

代码如下：

#include<stdio.h>
int num[1005];
int main()
{
    int n,m,x,y,i,j,k;
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&m);
        for(x=0;x<m;x++)
            scanf("%d",&num[x]);
        for(j=1;j<m;j++)
            for(k=0;k<m-j;k++)
                if(num[k]<num[k+1])
                {
                    int temp;
                    temp=num[k];
                    num[k]=num[k+1];
                    num[k+1]=temp;
                } 
        for(y=0;y<m;y++)
        {
            if(y==num[y]-1)
            {
                printf("%d\n",y+1);
                break;
            }
            if(num[y]-1<y)
            {
            	printf("%d\n",y);
            	break;
            }
        }
    }
}

---

总结

排序，找规律