1. 题目

PAT (Basic Level) Practice (中文): 1060

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

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

1.1. 输入格式:

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

1.2. 输出格式:

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

1.3. 输入样例:

10
6 7 6 9 3 10 8 2 7 8

1.4. 输出样例:

6

2. 作答

2.1. 代码

2.1.1. 第一次 超时代码

# include "stdio.h"

int min(int a, int b){
    return a>b?b:a;
}

int main(int argc, char *argv[]) {
    int i, j, n, time[100010]={0}, in;

    scanf("%d", &n);
    for (i = 1; i <= n ; ++i) {
        scanf("%d", &in);
        for (j = 0; j < min(n, in); ++j) {
            ++time[j];
        }
    }

    int res = 0;
    for (i = n; i; --i){
        if (time[i] >= i) {
            res = i;
            break;
        }
    }
    printf("%d\n", res);

    return 0;
}

2.1.2. AC代码

因为数据比较大,涉及到$10^{5}$这样的大数,因此需要找办法尽可能减少内层循环的次数。

# include "stdio.h"

int main(int argc, char *argv[]) {
    int i, j, n, time[100010]={0}, in;

    scanf("%d", &n);
    for (i = 1; i <= n ; ++i) {
        scanf("%d", &in);
        ++time[(in>n?n:in-1)];
    }

    int res = 0;
    for (i = n; i; --i){
        res+=time[i];
        if (res < i) continue;
        res = i;
        break;
    }
    printf("%d\n", res);

    return 0;
}

2.2. 评测结果

提交时间 状态 分数 题目 编译器 耗时 用户
2019/2/25 02:11:56 答案正确 25 1060 C (gcc) 23 ms soulans
测试点 结果 耗时 内存
0 答案正确 1 ms 636 KB
1 答案正确 1 ms 640 KB
2 答案正确 1 ms 632 KB
3 答案正确 23 ms 640 KB
4 答案正确 1 ms 636 KB
5 答案正确 1 ms 632 KB

3. 标答

今天灰灰考研没有发新文章。