1060 爱丁顿数 (25 分)-蒲公英云

1060 爱丁顿数 (25 分)

冷不防 2023-06-04 15:58 92阅读 0赞

题目：1060 爱丁顿数 (25 分)

英国天文学家爱丁顿很喜欢骑车。据说他为了炫耀自己的骑车功力，还定义了一个“爱丁顿数” E ，即满足有 E 天骑车超过 E 英里的最大整数 E。据说爱丁顿自己的 E 等于87。

现给定某人 N 天的骑车距离，请你算出对应的爱丁顿数 E（≤）。

输入格式：
输入第一行给出一个正整数 N (≤)，即连续骑车的天数；第二行给出 N 个非负整数，代表每天的骑车距离。

输出格式：
在一行中给出 N 天的爱丁顿数。

输入样例：
10
6 7 6 9 3 10 8 2 7 8
输出样例：
6

思路：

读懂题目真的很重要，不然就会像我一样，案例输进去跑出的结果是一样的，但是一个测试点都过不了QAQ。
题目想表达的是：第一天骑车距离超过1，则E就是1，第二天超过2，那E就是2了，第三天没超过3，那E还是2.（可能就是我理解力不好T^T，理解成另一个意思了我……）
案例输入的十天里，有六天满足这种情况，所以输出6 。注意：是超过！！不能等于。还算上等于的情况就只能过测试点0和2了。
按降序排序后判断和无序直接判断是差不多的，相比之下排完序后判断更好一点，因为一旦判到小于等于的情况就可以直接break，然后输出计数结果。
直接按这种无序判断的话测试点5会答案错误，应该是边界处没处理好，或者需要特判？？？（没试。想这么做的可以试试）

代码：

1 #include <cstdio>
 2 #include <cstring>
 3 #include <cctype>
 4 #include <iostream>
 5 #include <sstream>
 6 #include <cmath>
 7 #include <algorithm>
 8 #include <string>
 9 #include <stack>
10 #include <queue>
11 #include <vector>
12 #include <map>
13 using namespace std;
14 
15 int cmp(int a, int b)
16 {
17     return a > b;
18 }
19 
20 int main()
21 {
22     int n, e[100005];
23     scanf("%d", &n);
24     for(int i = 0; i < n; i++)
25     {
26         scanf("%d", &e[i]);
27     }
28     sort(e, e + n, cmp);
29     int sum = 0;
30     for(int i = 0; i < n; i++)
31     {
32         if(e[i] > i+1)
33             sum++;
34         else
35             break;
36     }
37     printf("%d\n", sum);
38     return 0;
39 }