PAT乙级1060 || 爱丁顿数（详解，C/C++示例，测试点分析）

Posted on In

爱丁顿数

题目描述

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

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

输入格式

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

输出格式

在一行中给出 N 天的爱丁顿数。

输入样例

1
2
10
6 7 6 9 3 10 8 2 7 8

输出样例

1
6

问题解决

解题思想

此题很容易想到暴力解法，从0开始遍历所有骑车距离，找到一个最大的满足有 E 天骑车超过 E 英里的最大整数 E。显然会有超时。

因此，需要思考高效的算法。设置数组num[]，下标i为骑车距离，对应内容存超过距离为i-1天数（即骑车距离为i的天数）；然后从最大骑车距离开始反向遍历骑车距离并统计超过i-1英里的天数d（递推统计，超过i英里的一定也超过i-1英里），直到骑车距离超过i-1英里的天数d不小于i-1，此时i-1即为E。

坑点提醒

题中没有给骑车距离的上限，因此骑车距离可能超过$10^5$，故maxn应设置的大一些，一开始我设置为100001，测试点3发生段错误，改为1000000后没有问题。

代码示例（C/C++）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
using namespace std;
const int maxn = 1000000;   //注意此处，题中没有给骑车距离的上限，设置为100001会有段错误
int main()
{
    int n,num[maxn]= {0};   //数组num下标i为骑车距离，对应内容存超过距离为"i-1"天数
    scanf("%d",&n);
    int maxi = 0;   //最大骑车距离
    for(int i = 0; i < n; i++) {
        int tmp;
        scanf("%d",&tmp);
        num[tmp]++;    //统计骑车距离为tmp的天数
        if(maxi < tmp){
            maxi = tmp;
        }
    }
    int d = 0;  //超过某骑车距离的天数，初始化为超过maxi的天数
    for(int i = maxi; i >= 0; i--) {
        d += num[i];
        if(d >= i - 1) {    //骑车距离超过i-1的天数d不小于i-1，此时i-1即为E
            printf("%d",i - 1);
            break;
        }
    }
    return 0;
}

题目来源：PAT乙级1060
作者：CHEN, Yue
单位：浙江大学

稀罕作者