Home PAT 1117 Eddington Number
Post
Cancel

PAT 1117 Eddington Number

Link

寻找 N 天中满足: 有 E 天的骑行距离大于 E 的最大的 E.

思路: 对输入数据从大到小排序, 则排序后的 a 数组表示: 前 i 天中骑行距离的最小值是 a[i]. 那么只要保证 a[i]>i 就行了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,e=1,a[100010];
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n,greater<int>());
    while(e<=n&&a[e]>e) e++;
    printf("%d\n",e-1);
    return 0;
}
This post is licensed under CC BY 4.0 by the author.