PTA刷题Basic篇——1060.爱丁顿数——Day(30)

题目描述

找出数组中的爱丁顿数，爱丁顿数E满足的要求是，在数组中有E个元素大于E。

题目分析

我们可以将i从1遍历到输入的N,判断其中是否有i个数大于i。找出最大的i即可。

但是这种方法时间复杂度有点高，所以我们换一种方法。

我们先给出E初始化为0，将数组从大到小排序。从第一个位置开始遍历，如果这个位置的公里数>E+1(E+1是天数)，则我们将E+1；否则，我们直接break退出，因为数组降序，后面一定不满足要求。

因为天数和索引存在一定关系，所以我们可以在遍历的过程中进行统计天数。

代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(int a, int b) {return a > b;}
int main()
{
    int n, tmp, E = 0;
    scanf("%d", &n);
    vector<int>v(n);
    for (int i = 0; i < n; i++)
    {
         scanf("%d", &tmp);
         v.push_back(tmp);
    }
    sort(v.begin(), v.end(), cmp);
    //可以通过遍历0-n找出一个值，赋值给E
    //也可以使用这种方法,先给定一个E,在遍历的过程中,E逐渐递增,如果公里数>E,则E继续递增
    for (int i = 0; i < n; i++)
    {
         if (v[i] <= E + 1) break;
         E++;
    }
    printf("%d", E);
    return 0;
}
           

答题用时8min

Q60——finish√