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√