【PAT甲级 - C++题解】1117 Eddington Number

简介: 【PAT甲级 - C++题解】1117 Eddington Number

1117 Eddington Number


British astronomer Eddington liked to ride a bike. It is said that in order to show off his skill, he has even defined an “Eddington number”, E – that is, the maximum integer E such that it is for E days that one rides more than E miles. Eddington’s own E was 87.


Now given everyday’s distances that one rides for N days, you are supposed to find the corresponding E (≤N).


Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤105), the days of continuous riding. Then N non-negative integers are given in the next line, being the riding distances of everyday.


Output Specification:

For each case, print in a line the Eddington number for these N days.


Sample Input:

10
6 7 6 9 3 10 8 2 7 8

Sample Output:

6


题意

给定 N 个数,需要我们找出一个最大的爱丁顿数 i ,其定义为当有 i 个数都大于 i 时,则 i 就是爱丁顿数。


思路

这道题可以先把这 N 个数放到数组 a 中并进行排序,然后对爱丁顿数进行枚举,因为最多只有 N 个数,所以爱丁顿数最大不会超过 N 。


每次枚举只需判断 a[N-i] 是否大于当前爱丁顿数 i ,如果大于,则说明第 N-i 个数及其以后的所有的共 i 个数都大于 i ,因为数组已经是有序的,前面的数大于 i 则后面的数也一定大于 i ,那么直接输出 i 即可。


代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int a[N];
int n;
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)    scanf("%d", &a[i]);
    sort(a, a + n);
    for (int i = n; i; i--)
        if (a[n - i] > i)
        {
            printf("%d\n", i);
            return 0;
        }
    puts("0");
    return 0;
}
目录
相关文章
|
C++
【PAT甲级 - C++题解】1040 Longest Symmetric String
【PAT甲级 - C++题解】1040 Longest Symmetric String
67 0
|
算法 C++
【PAT甲级 - C++题解】1044 Shopping in Mars
【PAT甲级 - C++题解】1044 Shopping in Mars
85 0
|
存储 C++ 容器
【PAT甲级 - C++题解】1057 Stack
【PAT甲级 - C++题解】1057 Stack
78 0
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
104 1
|
6月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
7月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
49 0
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
39 0
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
97 0
LeetCode 414. Third Maximum Number
|
存储
LeetCode 313. Super Ugly Number
编写一段程序来查找第 n 个超级丑数。 超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
102 0
LeetCode 313. Super Ugly Number
|
算法
LeetCode 306. Additive Number
累加数是一个字符串,组成它的数字可以形成累加序列。 一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外,字符串中的其他数都等于它之前两个数相加的和。 给定一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是累加数。 说明: 累加序列里的数不会以 0 开头,所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
127 0
LeetCode 306. Additive Number