傳送門

https://pintia.cn/problem-sets/994805260223102976/problems/994805269312159744

題目

英國天文學(xué)家愛丁頓很喜歡騎車。據(jù)說他為了炫耀自己的騎車功力，還定義了一個“愛丁頓數(shù)”E，即滿足有E天騎車超過E英里的最大整數(shù)E。據(jù)說愛丁頓自己的E等于87。
現(xiàn)給定某人N天的騎車距離，請你算出對應(yīng)的愛丁頓數(shù)E（<=N）。
輸入格式：
輸入第一行給出一個正整數(shù)N（<=10^5），即連續(xù)騎車的天數(shù)；第二行給出N個非負(fù)整數(shù)，代表每天的騎車距離。
輸出格式：
在一行中給出N天的愛丁頓數(shù)。
輸入樣例：
10
6 7 6 9 3 10 8 2 7 8
輸出樣例：
6

分析

這道題想了好久才用暴力法過了部分測試點，最后還是差一個測試點沒法通過，應(yīng)該是用來卡暴力法的，起初題意本身都理解不清楚（智商捉急）。
這里簡單“翻譯”一下：如果E天的騎車公里數(shù)均>天數(shù)E，那么這個E符合條件，現(xiàn)在可以有很多個E都符合這個條件，求符合條件的最大值E。
注意：如果輸入3 1 2 3。那么結(jié)果是1。因為大于1的天數(shù)是2天，大于2的天數(shù)是1天，大于3的天數(shù)是0天，所以只有E=1滿足E天騎車超過E英里，多余的天數(shù)可以不算，只要天數(shù)>=E即可，不非得是等于。另外在沒有符合條件的值是要輸出0。
具體的算法是對數(shù)組進(jìn)行降序排序，降序排列的好處是可以直接計算出最大E值。
首先根據(jù)樣例降序后為：10 9 8 8 7 7 6 6 3 2
1.用10和10的下標(biāo)1比較，10 > 1，所以有1天的騎車超過1英里；
2.用9和9的下標(biāo)2比較，9 > 2，所以有2天的騎車超過2英里（因為10 > 9，9符合，所以10肯定符合，后面同理）；
3.用8和8的下標(biāo)3比較，8 > 3，所以有3天的騎車超過3英里；
4.用8和8的下標(biāo)4比較，8 > 4，所以有4天的騎車超過4英里；
5.用7和7的下標(biāo)5比較，7 > 5，所以有5天的騎車超過5英里；
6.用7和7的下標(biāo)6比較，7 > 6，所以有6天的騎車超過6英里；
7.用6和6的下標(biāo)7比較，6 > 7不成立，所以最大值E為6。
這里需要注意的是，若全部滿足這個條件的話，要檢測遍歷到數(shù)組的結(jié)尾就停止，不能越界。

源代碼

//C/C++實現(xiàn)
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool compare(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(), compare); //desc
    int e = 0;
    int i = 1;
    while(i <= n && v[i] > i){
        ++e;
        ++i;
    }
    printf("%d\n", e);
    return 0;
}