PAT Basic 1060. 爱丁顿数

1. 题目描述：

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

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

2. 输入格式：

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

3. 输出格式：

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

4. 输入样例：

10
6 7 6 9 3 10 8 2 7 8

5. 输出样例：

6

6. 性能要求：

Code Size Limit
16 KB
Time Limit
250 ms
Memory Limit
64 MB

思路：

根据题目描述，爱丁顿数\(E\)的取值范围在\(0 \sim days\)之间，所以定义一个\(days+1\)大小的int数组记录每种候选值的合法天数。最后为找到最大整数\(E\)，倒序遍历数组，当合法天数大于等于当前整数时，输出爱丁顿数\(E\)。

这里第一次提交时testpoint3报segmentation fault，检查代码后发现递增合法天数时，没有限制上限，导致数组越界。改过来后testpoint3又报time limit exceeded，为缩短时间，额外定义了一个allFlag变量，即所有候补值的合法天数都需要递增时就不再遍历数组的每一个元素，而是直接递增allFlag，改过来后AC。

最后虽然AC了，但是感觉这种方法还是有些冗余，最后参考大佬题解：1060. 爱丁顿数(25)-PAT乙级真题_柳婼的博客-CSDN博客 ，她通过排序的思路得出了结果。

My Code:

#include <stdio.h>
#include <stdlib.h> // calloc header

// first submit testpoint3 segmentation fault.
// (Your program get a segmentation fault. Segfaults are caused by a program trying to read or write an illegal memory location.)
int main(void)
{
    int days=0;
    int *pInt = NULL;
    int i=0; // iterator
    int temp=0;
    int j=0; // iterator
    int allFlag = 0;
    
    scanf("%d", &days);
    
    pInt = (int *)calloc(days+1, sizeof(int)); // E in (0 ~ days), days+1 possibility
    
    for(i=0; i<days+1; ++i)
    {
        scanf("%d", &temp); // here forget to restrict temp, may cause out of range!!!
//         if(temp>days) temp = days; // here fixed segment fault, but testpoint3 cause time limit exceeded.
        if(temp>days) // here use allFlag fixed time limit exceeded.
        {
            ++allFlag;
        }
        else
        {
            for(j=0; j<temp; ++j)
            {
                ++pInt[j];
            }
        }

    }
    
    for(i=days; i>=0; --i)
    {
        if(pInt[i]-i +allFlag >= 0)
        {
            printf("%d", i);
            break;
        }
    }
    
    free(pInt);
    return 0;
}