【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
296 0
|
算法 C++
【PAT甲级 - C++题解】1044 Shopping in Mars
【PAT甲级 - C++题解】1044 Shopping in Mars
378 0
|
存储 C++ 容器
【PAT甲级 - C++题解】1057 Stack
【PAT甲级 - C++题解】1057 Stack
329 0
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
编译器 C++ 容器
【c++11】c++11新特性(上)(列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式)
C++11为C++带来了革命性变化,引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式,initializer_list简化了容器多元素初始化;右值引用和移动语义优化了资源管理,减少拷贝开销;类新增移动构造和移动赋值函数提升性能;lambda表达式提供匿名函数对象,增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展,提升了开发效率与程序性能。
740 12
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
410 16
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
436 0
|
存储 编译器 程序员
c++的类(附含explicit关键字,友元,内部类)
本文介绍了C++中类的核心概念与用法,涵盖封装、继承、多态三大特性。重点讲解了类的定义(`class`与`struct`)、访问限定符(`private`、`public`、`protected`)、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数(构造函数、析构函数、拷贝构造、赋值重载)以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员(变量与函数)、友元(友元函数与友元类)的概念及其使用场景,并简要介绍了内部类的特性。
642 0
|
安全 C++
【c++】继承(继承的定义格式、赋值兼容转换、多继承、派生类默认成员函数规则、继承与友元、继承与静态成员)
本文深入探讨了C++中的继承机制,作为面向对象编程(OOP)的核心特性之一。继承通过允许派生类扩展基类的属性和方法,极大促进了代码复用,增强了代码的可维护性和可扩展性。文章详细介绍了继承的基本概念、定义格式、继承方式(public、protected、private)、赋值兼容转换、作用域问题、默认成员函数规则、继承与友元、静态成员、多继承及菱形继承问题,并对比了继承与组合的优缺点。最后总结指出,虽然继承提高了代码灵活性和复用率,但也带来了耦合度高的问题,建议在“has-a”和“is-a”关系同时存在时优先使用组合。
1193 6