PAT A1117 Eddington Number(C++)

PAT甲级目录 | PAT乙级目录

题目描述

原题地址:A1117 Eddington Number
中文版:B1060 爱丁顿数

解题思路

对全部每天的公里数进行倒序排序,则大于第 $i$ ($i$ 从 0 开始)个公里数的天数有 $i - 1$ 天。最大的 E 即遇到的第一个“公里数小于等于天数” 的天数。

易错点

  • while(cnt < N && D[cnt] > cnt + 1) cnt++;
    • 也可以用 for 循环

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <cstdio>
#include <algorithm>
using namespace std;
bool cmp(int a, int b){ return a > b; }
int main(){
int N, D[100010] = {0}, cnt = 0;
scanf("%d", &N);
for(int i = 0; i < N; i++){
scanf("%d", &D[i]);
}
sort(D, D + N, cmp);
while(cnt < N && D[cnt] > cnt + 1) cnt++;
printf("%d\n", cnt);
return 0;
}