题意:给出了N个数字,确定一个尽可能大的数字E,要求这N个数字中大于E的数字有E个。
思路: 乍一看不知道题目在说啥。静下心来多读几遍题目,在草稿纸上比划比划,发现是个大水题。解释一下样例,原始序列为6 7 6 9 3 10 8 2 7 8,将其从大到小排序,则是10 9 8 8 7 7 6 6 3 2,(假设下标从1开始),我们这样来理解,第1天骑行10公里(说明有1天超过1);第2天骑行9公里(说明有2天超过2);第3天骑行8公里(说明有3天超过3)...,第6天骑行7公里(说明有6天超过6);第7天骑行6公里(有7天超过7???错了。。退出。。),因此这种情况答案是6,就是这10天中有6天骑行的距离是大于6的。
另外再举几个例子,比如:1 1 1 1,第1天骑行1公里(有1天超过1?不满足,退出),因此这种情况答案是0;再比如:2 2 2 2,第1天骑行2公里(有1天超过1),第2天骑行2公里(有2天超过2?不满足,退出),答案是1。
代码:
#include#include using namespace std;const int maxn=100005;int dis[maxn];bool cmp(int a,int b) { return a>b;}int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&dis[i]); sort(dis+1,dis+n+1,cmp); int i=1; while(dis[i]>i) i++; printf("%d",i-1); return 0;}