PAT乙级真题 — 1060 爱丁顿数（java）

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

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

输入格式：

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

输出格式：

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

输入样例：

10
6 7 6 9 3 10 8 2 7 8

输出样例：

6

思路：参考了柳婼大神的做法，先将里程数从大到小排序，用Arrays.sort定制排序的话需要确保数据类型为包装类，所以用了Integer存储数据，可知满足爱丁顿的天数范围在[0,N]天，这里要求的是天数，所以当数组中的值大于其下标+1——>爱丁顿天数+1

然后用java完成测试点3会超时，看了别人的说法是因为所有天数大于其最大英里数，所以可以用一个大数遍历输入，如果这个大数遍历完后仍然大于天数总和，直接输入天数总和并退出程序，这样就不用进入循环导致超时。

代码：

import java.io.*;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static int ini() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
    public static void main(String[] args) throws IOException {
        int min = Integer.MAX_VALUE;
        int N = ini();
        Integer[] num = new Integer[N];
        for (int i = 0; i < N; i++) {
            num[i] = ini();
            min = num[i] > min ? min : num[i];
        }
        if(min > N) {
            System.out.println(N);
        }else{
            Arrays.sort(num,new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        int n = 1, day = 0;
        while(N >= day && num[n - 1] > n) {
            n++;
            day++;
        }
            System.out.println(day);
        }
    }
}

运行结果：

原文地址：https://blog.csdn.net/2403_89522296/article/details/145291082

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！