1060 爱丁顿数

pat乙级 1060 爱丁顿数

英国天文学家爱丁顿很喜欢骑车。据说他为了炫耀自己的骑车功力，还定义了一个“爱丁顿数” E ，即满足有 E 天骑车超过 E 英里的最大整数 E。据说爱丁顿自己的 E 等于87。

现给定某人 N 天的骑车距离，请你算出对应的爱丁顿数 E（≤N）。

输入格式： 输入第一行给出一个正整数 N (≤10​⁵)，即连续骑车的天数；第二行给出 N 个非负整数，代表每天的骑车距离。

输出格式： 在一行中给出 N 天的爱丁顿数。

输入样例1：

10 6 7 6 9 3 10 8 2 7 8

输出样例1：

6

总结： 题目理解很重要!! 满足有 E 天骑车超过 E 英里的最大整数 E 有E天骑车超过E英里，有E天就行，不一定要等于E天，可以大于等于E天

所以从大到小排序骑行的英里数，设置计数器，如果刚好有E天，则不用关心后面的骑行英里数，直接退出循环

AC代码：

#include<iostream> #include<vector> #include<string> #include<map> #include<algorithm> #include<math.h> #include<iomanip> using namespace std; bool cmp(int a, int b){ return a > b; } int main(){ int n; cin>>n; vector<int> v; for(int i=0;i<n;i++){ int in; cin>>in; v.push_back(in); } sort(v.begin(),v.end(),cmp); int e; for(int i=n;i>0;i--){ int flag=0; int count=0; for(int j=0;j<n;j++){ if(v[j]>i){ count++; } if(count==i){ flag=1; break; } } if(flag==1){ e=i; break; } } cout<<e; return 0; }