1117 Eddington Number

British astronomer Eddington liked to ride a bike. It is said that in order to show off his skill, he has even defined an “Eddington number”, E – that is, the maximum integer E such that it is for E days that one rides more than E miles. Eddington’s own E was 87.

Now given everyday’s distances that one rides for N days, you are supposed to find the corresponding E (≤N).

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤105), the days of continuous riding. Then N non-negative integers are given in the next line, being the riding distances of everyday.

Output Specification:

For each case, print in a line the Eddington number for these N days.

Sample Input:

10
6 7 6 9 3 10 8 2 7 8

Sample Output:

6

题意

给定 N 个数，需要我们找出一个最大的爱丁顿数 i ，其定义为当有 i 个数都大于 i 时，则 i 就是爱丁顿数。

思路

这道题可以先把这 N 个数放到数组 a 中并进行排序，然后对爱丁顿数进行枚举，因为最多只有 N 个数，所以爱丁顿数最大不会超过 N 。

每次枚举只需判断 a[N-i] 是否大于当前爱丁顿数 i ，如果大于，则说明第 N-i 个数及其以后的所有的共 i 个数都大于 i ，因为数组已经是有序的，前面的数大于 i 则后面的数也一定大于 i ，那么直接输出 i 即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n;
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)    scanf("%d", &a[i]);
    sort(a, a + n);
    for (int i = n; i; i--)
        if (a[n - i] > i)
        {
            printf("%d\n", i);
            return 0;
        }
    puts("0");
    return 0;
}