[C++知识库]个人练习-PAT甲级-1117 Eddington Number

题目链接https://pintia.cn/problem-sets/994805342720868352/problems/994805354762715136

题目大意，给出一个人连续骑行N天的数据，求最大的E，使得骑行公里数大于E的天数至少有E天。

用一个数组days[]存储骑行距离大于下标dis的天数。第一遍扫描时只能得到如days[100]=2,days[99]=3这样的数据，但实际上days[99]应该为5。另外，如果某天公里数超过了总天数，要将它算进days[N]里。比如总共一百天，某天你骑了120公里，那么由于E<=N，我们不会考虑数组days[]里下标比N大的元素，这一天依然是算进days[100]里。

    for (int day = 1; day <= N; day++) {
        int dis;
        scanf("%d", &dis);
        if (dis > N)
            days[N]++;
        else
            days[--dis]++;
    }

之后从后往前遍历，最后一天N的数据已经是正确了的。如果N不满足，那么先计算N-1天的数据，然后再考虑N-1天。即距离大于100的天数加到大于99的天数里，这样才完整。这样如果完整遍历下来，得到的days[]数组就是正确的。当然我们只要最大的满足要求的数字，得到E之后break就好。

    for (int day = N; day > 0; day--) {
        if (days[day] >= day) {
            E = day;
            break;
        }
        else
            days[day-1] += days[day];
    }

看了柳神等的做法是先排序然后扫描，这样省空间。我的话开了个数组，用空间换时间，省去了排序的O(NlogN)时间，扫描（不到）一遍就行。各有利弊，看情况吧。

完整代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>


using namespace std;

int days[100001];

int main() {
    int N, E = 0;
    scanf("%d", &N);
    for (int day = 1; day <= N; day++) {
        int dis;
        scanf("%d", &dis);
        if (dis > N)
            days[N]++;
        else
            days[--dis]++;
    }

    for (int day = N; day > 0; day--) {
        if (days[day] >= day) {
            E = day;
            break;
        }
        else
            days[day-1] += days[day];
    }

    printf("%d", E);

    return 0;
}