PAT (Advanced Level) Practice 1117 Eddington Number (25 分) 凌宸1642

本文主要是介绍PAT (Advanced Level) Practice 1117 Eddington Number (25 分) 凌宸1642，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

PAT (Advanced Level) Practice 1117 Eddington Number (25 分) 凌宸1642

题目描述：

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).

译：英国科学家爱丁顿喜欢骑行。据说为了展示他的技巧，他定义了一个"爱丁顿数"，E —— 满足 E 天 骑行多余 E 公里 的最大的整数。爱丁顿自己的 E 是 87。现在给定 N 个每天的骑行距离，你应该找出相应的 E (≤N) 。

Input Specification (输入说明):

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

译：每个输入文件包含一个测试用例。 对于每个用例，第一行给定一个正整数 N (≤10⁵)，表示贡献骑行的天数。接下来一行给定 N 个非负整数，表示每天的骑行距离。

output Specification (输出说明):

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

译：对于每个测试用例，在一行中输出这 N 天的爱丁顿数。

Sample Input (样例输入):

10
6 7 6 9 3 10 8 2 7 8

Sample Output (样例输出):

6

The Idea：

• 其实就是问，一个序列中，满足有 E 个数 大于E 的最大的 E 是多少。
• 将 N 个数按从大到小排序，然后依次遍历，如果第 i 个数 小于等于 i ，那么久表示这之前的所有数，都比 i - 1 大，所以最大的 E 就是本题的解。

The Codes:

#include<bits/stdc++.h>
using namespace std ;
vector<int> num ;
int n ; 
bool cmp(int a, int b){
	return a > b ;
}
int main(){
	scanf("%d" , &n) ;
	num.resize(n + 1) ;
	for(int i = 1 ; i <= n ; i ++) scanf("%d" , &num[i]) ;
	sort(num.begin() + 1 , num.end() + 1, cmp) ; // 从大到小排序
	for(int i = 1 ; i <= num.size() ; i ++){
		if(num[i] <= i){
			cout << i - 1 << endl ;
			break; 
		}
	}
	return 0 ;
}

这篇关于PAT (Advanced Level) Practice 1117 Eddington Number (25 分) 凌宸1642的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！