PAT B1060 爱丁顿数(C++)

PAT甲级目录 | PAT乙级目录

题目描述

B1060 爱丁顿数

解题思路

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

易错点

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

代码示例：

#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;
}