一、题目描述
原题链接
Input Specification:
Output Specification:
Sample Input
10 6 7 6 9 3 10 8 2 7 8
Sample Output:
6
二、解题思路
一道巧妙的数学题，给我们一组数据，要我们找到最大的E，使得这组数字里有E个大于E的数。题目给的时间是250ms，如果我们直接遍历的话，很有可能会超时，我们这里可以换个思路。将所有数字从大到小排序，按顺序遍历，找到第一个数字小于下标的数，随后输出前一个数的下标即可。因为我们只需要找出超过E的数，与输入顺序无关，我们从大到小排序并不会影响结果，从小到大排序后，事实上下标就起到了一个计数的作用，比如下标为5的数字为6，而还没有退出程序，则说明第5天的骑行长度大于5，随后遍历到下标为6的数，假设其为6，那么我们就退出循环，因为6公里并不大于天数，而后面也不会有大于6的数了。基于这个思想，可写出十分简单的代码。
三、AC代码
#include<iostream>
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
using namespace std
;
bool cmp(int a
, int b
)
{
return a
> b
;
}
int main()
{
int N
;
scanf("%d", &N
);
vector
<int> v(N
+1);
for(int i
=1; i
<=N
; i
++)
scanf("%d", &v
[i
]);
sort(v
.begin()+1, v
.end(), cmp
);
for(int i
=1; i
<=N
; i
++)
{
if(v
[i
] <= i
)
{
printf("%d", i
-1);
return 0;
}
}
printf("%d", N
);
return 0;
}
