PAT乙级1030

题目链接

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/

欢迎讨论和交流!

---