「PAT乙级真题解析」Basic Level 1060 爱丁顿数 (问题分析+完整步骤+伪代码描述+提交通过代码)
题设要求统计所有满足E天超过E英里的整数E, 然后给出E的最大值. 求一组数中的最大值是一个常规的过程, 所以本题的核心是如果统计所有E天超过E英里的E. 题设给出的数据形式是第i天跑了j英里, 我们需要统计的是跑超过j英里的天数. 所以我们需要先统计跑了j英里的天数, 然后从最大的距离开始, 将该距离加到小于这个距离的所有距离的天数统计中.
#算法#数据结构#需求分析#pat考试#c语言
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
问题分析
题设要求统计所有满足E天超过E英里的整数E, 然后给出E的最大值. 求一组数中的最大值是一个常规的过程, 所以本题的核心是如果统计所有E天超过E英里的E.
题设给出的数据形式是第i天跑了j英里, 我们需要统计的是跑超过j英里的天数. 所以我们需要先统计跑了j英里的天数, 然后从最大的距离开始, 将该距离加到小于这个距离的所有距离的天数统计中.
以样例输入为例: 6 7 6 9 3 10 8 2 7 8, 将有统计结果如下:
10: 1 (跑了1天10公里) = 1
9: 2 (1天10公里 + 1天9公里) = (1 + 1) = 2
8: 4 (10 * 1 + 9 * 1 + 8 * 2) = (2 + 2) = 4
7: 6 (...) = (4 + 2) = 6
6: 8 ...
3: 9 ...
2: 10 ...
如果统计结果中右边的天数大于左边的距离数, 则满足条件, 然后最后一个满足条件的就是题设要求的结果。 (如果是倒序检查, 则第一个满足条件的是要求的结果)
完整描述步骤
- 获取输入: 运动天数, 每天的运动距离
- 统计每一个距离值出现的次数
- 从最大的距离j开始进行如下操作:
- 将跑了超过距离j的天数加上跑了j的天数, 得到跑达到距离j的天数
- 检查天数是否大于j-1(因为要求是"超过"的关系, 所以跟j-1比较), 如果是, 则得到答案
- 否则对下一个距离值进行检查
- 输出结果
伪代码描述
-
get input: day_amount, distance of each day
-
init counter and max_distance as 0;
-
for each distance:
- counter[distance]++
- if distance > max_distance: max_distance = distance
-
for distance in range(max_distance, min_distance - 1, step=-1):
- if distance != max_distance:
- counter[distance] += counter[distance]
- if counter[distance] > distance - 1:
- print(distance)
- break
- if distance != max_distance:
注意事项
题目说给定的N不超过10^5, 但是设置数组长度为10^5 + 10会出现段错误, 长度改成1000000后解决. 盲猜可能是题目写的10^5, 但设置测试用例的时候记成了10^6, 才会出现矛盾。
完整提交代码
/*
# 问题分析
题设要求统计所有满足E天超过E英里的整数E, 然后给出E的最大值.
求一组数中的最大值是一个常规的过程, 所以本题的核心是如果统计所有E天超过E英里的E.
题设给出的数据形式是第i天跑了j英里, 我们需要统计的是跑超过j英里的天数.
所以我们需要先统计跑了j英里的天数, 然后从最大的距离开始, 将该距离加到小于这个距离的所有距离的天数统计中.
以样例输入为例: 6 7 6 9 3 10 8 2 7 8, 将有统计结果如下:
10: 1 (跑了1天10公里) = 1
9: 2 (1天10公里 + 1天9公里) = (1 + 1) = 2
8: 4 (10 * 1 + 9 * 1 + 8 * 2) = (2 + 2) = 4
7: 6 (...) = (4 + 2) = 6
6: 8 ...
3: 9 ...
2: 10 ...
如果统计结果中右边的天数大于左边的距离数, 则满足条件, 然后最后一个满足条件的就是题设要求的结果。
(如果是倒序检查, 则第一个满足条件的是要求的结果)
# 完整描述步骤
1. 获取输入: 运动天数, 每天的运动距离
2. 统计每一个距离值出现的次数
3. 从最大的距离j开始进行如下操作:
- 将跑了超过距离j的天数加上跑了j的天数, 得到跑达到距离j的天数
- 检查天数是否大于j-1(因为要求是"超过"的关系, 所以跟j-1比较), 如果是, 则得到答案
- 否则对下一个距离值进行检查
4. 输出结果
# 伪代码描述
1. get input: day_amount, distance of each day
2. init counter and max_distance as 0;
3. for each distance:
- counter[distance]++
- if distance > max_distance: max_distance = distance
4. for distance in range(max_distance, min_distance - 1, step=-1):
- if distance != max_distance:
- counter[distance] += counter[distance]
- if counter[distance] > distance - 1:
- print(distance)
- break
# 注意事项
题目说给定的N不超过10^5, 但是设置数组长度为10^5 + 10会出现段错误, 长度改成1000000后解决.
盲猜可能是题目写的10^5, 但设置测试用例的时候记成了10^6, 才会出现矛盾。
*/
# include<stdio.h>
int main(){
int counter[1000000] = {0};
int day_amount;
scanf("%d", &day_amount);
int max_distance;
int distance;
for (int i = 0; i < day_amount; i++){
scanf("%d", &distance);
counter[distance]++;
if (distance > max_distance)
max_distance = distance;
}
for (int i = max_distance; i > 0; i--){
counter[i] += counter[i+1];
if (counter[i] >= i - 1){
printf("%d", i - 1);
break;
}
}
return 0;
}