「PAT乙级真题解析」Basic Level 1030 完美数列 (问题分析+完整步骤+伪代码描述+提交通过代码)
题设给定一个正整数数列, 要求找出从中尽可能多的数组成一个数列,使得新数列满足指定条件。 即, 新数列的最大值 小于等于 新数列的最小值 乘以 给定系数p. 由于数列和系数p是给定的, 变量是选取不同子数列后所对应的最大值和最小值。 所以这是一个找满足指定条件的一对数作为最大值和最小值的问题。
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
PAT乙级BasicLevelPractice 1030 完美数列
问题分析
题设给定一个正整数数列, 要求找出从中尽可能多的数组成一个数列,使得新数列满足指定条件。 即, 新数列的最大值 小于等于 新数列的最小值 乘以 给定系数p.
由于数列和系数p是给定的, 变量是选取不同子数列后所对应的最大值和最小值。 所以这是一个找满足指定条件的一对数作为最大值和最小值的问题。 因为有最大值最小值之后, 只要把值在最值区间的数都放入新数列就即是满足条件的队列。 而要让数列元素尽可能多,就需要让最值区间范围尽可能大,也就是需要让最大值和最小值差值尽可能大。 由于给定的数列值不是连续的,所以我们需要将数列先排序,然后用最大值最小值的索引位置差距来计算数列元素个数。 (排序后的数列, 需要选择索引为i的元素和索引为i+n的元素作为最小值和最大值, 则元素个数为(n+1) = (i+n) - i + 1)
最直接的方法就是我们对所有可能的组合(number_1, number_2)进行计算, 然后记录组成新数列元素最多的一个。 可以优化的是, 如果我们当前已经找到满足条件的数列最长为n个元素, 则下次查找时, 可以从最小值之后n个元素开始选择作为最大值。 这样可以跳过那些尽管满足条件, 但是数列元素个数不会超过n个的情况。
完整描述步骤
- 获取输入: 数列以及系数p
- 将序列从小到大排序
- 设置数列元素个数计数器初始值为-1;
- 遍历所有的数对(i, j) (不妨设i <= j): 如果 (i, j)满足 j <= i*p, 则符合条件: 如果元素个数(j-i+1)大于当前计数器记录的最多元素个数, 则更新计数器的值
- 遍历完毕后, 输出计数器记录的最大值作为答案.
伪代码描述
- get input: number_amount, numbers, p;
- sort numbers asendingly
- max_element_amount = 0;
- for (int i = 0; i < number_amount; i++): for (int j = i + max_element_amount; j < number_amount; j++): if (j - i + 1) > max_element_amount: max_element_amount = j - i + 1;
- print max_element_amount
完整提交代码
/*
# 问题分析
题设给定一个正整数数列, 要求找出从中尽可能多的数组成一个数列,使得新数列满足指定条件。
即, 新数列的最大值 小于等于 新数列的最小值 乘以 给定系数p.
由于数列和系数p是给定的, 变量是选取不同子数列后所对应的最大值和最小值。
所以这是一个找满足指定条件的一对数作为最大值和最小值的问题。
因为有最大值最小值之后, 只要把值在最值区间的数都放入新数列就即是满足条件的队列。
而要让数列元素尽可能多,就需要让最值区间范围尽可能大,也就是需要让最大值和最小值差值尽可能大。
由于给定的数列值不是连续的,所以我们需要将数列先排序,然后用最大值最小值的索引位置差距来计算数列元素个数。
(排序后的数列, 需要选择索引为i的元素和索引为i+n的元素作为最小值和最大值, 则元素个数为(n+1) = (i+n) - i + 1)
最直接的方法就是我们对所有可能的组合(number_1, number_2)进行计算, 然后记录组成新数列元素最多的一个。
可以优化的是, 如果我们当前已经找到满足条件的数列最长为n个元素, 则下次查找时, 可以从最小值之后n个元素开始选择作为最大值。
这样可以跳过那些尽管满足条件, 但是数列元素个数不会超过n个的情况。
# 完整描述步骤
1. 获取输入: 数列以及系数p
2. 将序列从小到大排序
3. 设置数列元素个数计数器初始值为-1;
4. 遍历所有的数对(i, j) (不妨设i <= j):
如果 (i, j)满足 j <= i*p, 则符合条件:
如果元素个数(j-i+1)大于当前计数器记录的最多元素个数, 则更新计数器的值
5. 遍历完毕后, 输出计数器记录的最大值作为答案.
# 伪代码描述
1. get input: number_amount, numbers, p;
2. sort numbers asendingly
3. max_element_amount = 0;
4. for (int i = 0; i < number_amount; i++):
for (int j = i + max_element_amount; j < number_amount; j++):
if (j - i + 1) > max_element_amount:
max_element_amount = j - i + 1;
5. print max_element_amount
*/
#include <stdio.h>
int cmp(const void *a, const void *b)
{
return (*(int *)a - *(int *)b);
}
int main()
{
int number_amount;
long long p;
scanf("%d %lld", &number_amount, &p);
int numbers[number_amount];
for (int i = 0; i < number_amount; i++)
{
scanf("%d", &numbers[i]);
}
qsort(numbers, number_amount, sizeof(int), cmp);
int max_element_amount = 0;
int current_element_amount = 0;
for (int i = 0; i < number_amount; i++)
{
for (int j = i + max_element_amount; j < number_amount; j++)
{
if (numbers[j] <= numbers[i] * p)
{
current_element_amount = j - i + 1;
if (current_element_amount > max_element_amount)
max_element_amount = current_element_amount;
}
else
{
break;
}
}
}
printf("%d", max_element_amount);
return 0;
}