PAT乙级练习题1030 完美数列_给定一个正整数数列,和正整数 p,设这个数列中的最大值是 m,最小值是 m,如果 m≤mp-CSDN博客

本文链接：https://blog.csdn.net/Snapdragon123/article/details/120134425

题目：

给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mp，则称这个数列是完美数列。

现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。

输入格式：

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

输出格式：

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

输入样例：

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

输出样例：

思路历程：

最开始的思路是将数组排好序，通过两个for循环来查找每个位置的数字满足完美数列的最大长度，但是这样一一枚举很可能运行超时。所以就没有进行下去。
看了网上的解析，有个方法是利用二分查找法找到每个位置上满足完美数列的最大长度，降低了时间复杂度就可以避免出现运行超时了。
或者用双指针法，由于数组有序，完美数列的长度只能向前扩大，因此只需比较之前已经得到的最大长度是否满足完美数列，如果满足则继续扩大长度，直至不满足。

踩坑：

两个10⁹的数相乘可能超过int的数据范围，需要转换为long long类型，否则最后一个测试点过不去。
使用二分法最后得到的长度是mid-i，而不是mid-i+1

代码：

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, p;
    
    cin >> N >> p;
    int nums[N];
    
    for(int i = 0; i < N; ++i){
        cin >> nums[i];
    }
    
    sort(nums, nums+N);
    
    long long result;
    int max_length = 0;
    for(int i = 0; i < N; ++i){
        //在区间[i,N]查找满足条件的最右端点
        int left = i;
        int right = N;
        int mid;
        //需要转换为long long类型
        result = (long long)nums[i]*p;
        while(left <= right){
            mid = (left+right)/2;
            if(nums[mid] <= result){
                //如果满足M≤mp，因为要查找满足该条件的最大长度，因此继续向右半区域查找
                left = mid + 1;
            }
            else{
                //如果不满足，说明满足M≤mp的端点在左半区域，因此向左半区域查找
                right = mid - 1;
            }
        }
        max_length = max(max_length, mid-i);
    }
    
    cout << max_length;
    
    return 0;
}

双指针法思想：

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, p;
    
    cin >> N >> p;
    int nums[N];
    
    for(int i = 0; i < N; ++i){
        cin >> nums[i];
    }
    
    sort(nums, nums+N);
    
    long long result;
    int max_length = 0;
    for(int i = 0; i < N; ++i){
        //对于每个位置的数字，在已求得的最大长度的基础上，判断是否是完美数列
        for(int j = i+max_length; j < N; ++j){
            result = (long long)nums[i]*p;
            if(nums[j] <= result){
                max_length = max(max_length, j-i+1);
            }
            else{
                //如果不满足完美数列，直接退出，内循环后面的数字就不用遍历判断了
                break;
            }
        }
    }
    
    cout << max_length;
    
    return 0;
}

双指针法：

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, p;
    
    cin >> N >> p;
    int nums[N];
    
    for(int i = 0; i < N; ++i){
        cin >> nums[i];
    }
    
    sort(nums, nums+N);
    
    long long result;
    int max_length = 0;
    //j在外面定义，记录上一次的最大长度的位置
    int j = 0;
    for(int i = 0; i < N; ++i){
        result = (long long)nums[i]*p;
        while(j < N && nums[j] <= result){
            ++j;
        }
        max_length = max(max_length, j-i);
    }
    
    cout << max_length;
    
    return 0;
}

学到和回忆了：

双指针法
二分查找法
<bits/stdc++.h>头文件：包含了C++所有头文件的一个头文件
C++中的max函数和upperbound函数

max(a,b);//返回a和b的最大值
ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,
const T& val);//使用二分查找法查找指定范围内的第一个超过val的元素，返回迭代器，需减去第一个迭代器才能得到下标