题目链接

https://pintia.cn/problem-sets/994805260223102976/problems/994805292322111488

题解

emm刚开始思路有点错误，我直接将从小到大排序后的数列首个元素作为数列的最小值，但其实不是，数列第一个元素的不同可能会导致更大的完美数列长度。(参考链接：https://blog.csdn.net/chenyvye/article/details/78701846)

要注意的有三点：

1. 就是上边我错的那个
2. 用long long类型保存这些整数（\(10^9\)）
3. 移动序列时序列首位直接设为i+maxLen

// PAT BasicLevel 1030
// https://pintia.cn/problem-sets/994805260223102976/problems/994805291311284224

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    // 获取n和p
    int n;
    long long p;
    cin >> n >> p;
    
    // 获取数列
    long long *nums = new long long[n];
    for(int i=0;i<n;++i){
        cin >> nums[i];
    }

    // 排序
    sort(nums + 0, nums + n);

    // 寻找完美数列最大长度
    int j,maxLen=0;
    for (int i = 0; i < n; ++i){
        for(j=i+maxLen;j<n;++j){// 至少要比之前求出来的最大长度长，所以j初始化为i+maxLen
            if (nums[j] <= nums[i] * p){
                // 更新最长长度
                if (j - i + 1>maxLen){
                    maxLen = j - i + 1;
                }
            }
            // 出现非完美数列，之后也一定都是非完美数列，所以直接跳出循环
            else{
                break;
            }
        }

    }

    // 输出结果
    cout << maxLen;

    // 释放内存
    delete[] nums;

    //system("pause");
    return 0;
}

作者：@臭咸鱼

转载请注明出处：https://www.cnblogs.com/chouxianyu/

欢迎讨论和交流!

PAT乙级1030

原文：https://www.cnblogs.com/chouxianyu/p/11318429.html