PAT A1117 Eddington Number(C++)

发表于 | 分类于 | |
字数统计: 187 字 | 阅读时长 ≈ 1 分钟
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;
}