PAT乙级1030 || 完美数列（详解，C/C++示例，测试点分析）

Posted on In

完美数列

题目描述

给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M ≤ mp，则称这个数列是完美数列。
现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

输入格式

输入第一行给出两个正整数 N 和 p，其中 N（≤$10^5$）是输入的正整数的个数，p（≤$10^9$）是给定的参数。第二行给出 N 个正整数，每个数不超过 $10^9$。

输出格式

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入样例

1
2
10 8
2 3 20 4 5 1 6 7 8 9

输出样例

1
8

问题解决

解题思想

方法一：递归方法，测试点4会超时

注意参数p和数组a[]要定义成long或long long型，否则会导致测试点5不通过，想一下为什么？输入后先对数组a[]进行升序排序，然后递归调用函数Max_Per_Array()：

  1. 终止条件：a[j] <= p x a[i]，满足则直接返回j-i+1；
  2. 递归条件：a[j] > p x a[i]，先后判断最大值前移一位满足而最小值后移一位不满足和最大值前移一位不满足而最小值后移一位满足这两个条件是否满足，若满足，则只需进行相应的单个调用即可，若都不满足，则依次进行两个调用，返回最大的即可。

此法思路很简单，但是，运行效率不高，提交时测试点4会超时，因此有下面更高效的方法。
方法二：优化双层循环方法
先初始化完美数列最多元素个数，至少为1个；用双层循环，i从0开始依次递加作外层循环，a[i]为最小值，对于每一个i，j从i+max_coun开始，a[j]为最大值，判断是否满足完美数列的条件，若满足，则更新max_coun为当前完美数列的元素个数，即j-i+1，然后继续累加j继续判断直到跳出内层循环；若不满足，则直接跳出内存循环，因为若当前的j不满足，则后面的最大值更大，必不满足。
此法效率较高，不会出现超时。

代码示例（C/C++）

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
//递归方法，测试点4会超时
#include <cstdio>
#include <algorithm>
#define MAXN 100001
using namespace std;
int Max_Per_Array(long a[],int i,int j,long p);
int main()
{
    int n;
    long p;//定义为long型
    scanf("%d%ld",&n,&p);
    long a[MAXN];//定义为long型
    for(int i = 0; i < n; i++){
        scanf("%ld",&a[i]);
    }
    sort(a,a+n);//升序排序
    int max_coun;
    max_coun = Max_Per_Array(a,0,n-1,p);
    printf("%d",max_coun);
    return 0;
}
//返回数组a[]从第i到第j个位置能构成完美数列的最大元素个数
int Max_Per_Array(long a[],int i,int j,long p)
{
    if(a[j] <= p * a[i]){//满足完美数列
        return j-i+1;
    }
    else{//不满足完美数列
        if(a[j - 1] > p * a[i]&&a[j] <= p * a[i + 1]){//最大值前移一位满足而最小值后移一位不满足
            return Max_Per_Array(a,++i,j,p);//直接让最小值后移一位
        }
        else if(a[j - 1] <= p * a[i]&&a[j] > p * a[i + 1]){//最大值前移一位不满足而最小值后移一位满足
            return Max_Per_Array(a,i,--j,p);//直接让最大值前移一位
        }
        else{//最大值前移一位或最小值后移一位都不满足则分别前移和后移
            int ch_min,ch_max;
            ch_min = Max_Per_Array(a,++i,j,p);
            ch_max = Max_Per_Array(a,i,--j,p);
            return ch_min > ch_max ? ch_min : ch_max;//返回最大元素个数
        }
    }
}

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//优化双层循环方法，全部通过测试点
#include <cstdio>
#include <algorithm>
#define MAXN 100001
using namespace std;
int main()
{
    int n;
    long p;
    scanf("%d%ld",&n,&p);
    long a[MAXN];
    for(int i = 0; i < n; i++){
        scanf("%ld",&a[i]);
    }
    sort(a,a+n);//升序排序
    int max_coun = 1;//完美数列最多元素个数，至少1个
    for(int i = 0; i < n; i++){
        for(int j = i + max_coun; j < n; j++){//最大值从最小值位置加上当前完美数列最多元素个数处开始即可
            if(a[j] <= a[i] * p){//满足完美数列
                max_coun = j - i + 1;//更新最多元素个数
            }
            else{//不满足直接跳出循环，j再往后，最大值会更大，更不会满足
                break;
            }
        }
    }
    printf("%d",max_coun);
    return 0;
}

题目来源：PAT乙级1030
作者：CHEN, Yue
单位：浙江大学

稀罕作者