PAT-Basic 完美数列(25) 二分法和双指针c++解题思路

分析

这道题目首先需要考虑选择尽可能多的数构成一个完美数列。而它的条件又仅需要最大，最小值参与，比较能联想到需要用到排序，接下来按照循环去做。

优化

不考虑排序，仅考虑这个循环查找算法，它的时间复杂度达到了，如何优化它是接下来考虑的问题。这里有介绍两个方法二分查找和双指针法。

二分查找

二分查找的基本思路不用再说了，但是在实践中注意几个细节有利于简化思路：

• 虽然查找条件while(low <= high)也可以写成while(low < high)，但是两者有区别，当前者未找到时，low和high处于第一次low>high的状态；而后者处于low==high的状态。这里统一下，用第一种方法，后面会说为什么这么做。

• 总是在和之间查找元素。对于mid判断完毕后，不用再包含mid。

二分查找（查找不到返回-1）

//A为递增数列，x为欲查询的数，函数返回查找到的索引，未查找到返回-1
int binarySearch(int a[],int low,int high,int x){
    while (low <= high){
        int mid = low + (high - low) / 2;
        if (a[mid] < x){
            low = mid + 1;
        }
        else if (a[mid] > x){
            high = mid - 1;
        }
        else
            return mid;
    }
    return -1;
}

二分查找扩展

基于二分查找，可以进一步扩展两个方法。

• 查找第一个大于或等于x的元素位置

• 查找第一个大于x的元素位置

查找第一个大于或等于x的元素位置

//A为递增数列，x为欲查询的数，函数返回查找到的索引，未查找到返回-1
int binarySearch(int a[],int low,int high,int x){
    while (low <= high){
        int mid = low + (high - low) / 2;
        if (a[mid] < x){
            low = mid + 1;
        }
        else if (a[mid] >= x){// <-- if (a[mid] > x)
            high = mid - 1;
        }
        // else return mid;
    }
    return low;// <-- return -1
}

这里修改了三处：第一，修改了return -1为return low；第二，修改条件if (a[mid] > x)为if (a[mid] >= x)；第三，删除条件return mid。

分析：

查找第一个大于或等于x的元素位置，将条件if (a[mid] > x)改为if (a[mid] >= x)，对于只要大于等于x的位置，都在其左半部分查找（降低high）。该条件会导致高位high不断向左靠近，直到最后一个小于x的位置。

最终，high和low均指向最后一个小于x的位置。这里要解释下上面为什么while条件中使用(low<=high)，当while (low == high)成立，条件满足if (a[mid] < mp) low = mid + 1;，所以最终能通过low返回第一个大于等于x的索引位置。其目的就是为了保证low在等于high（指向最后一个小于x的位置）时，仍可以多一步运算而指向第一个大于等于的元素。

查找第一个大于x的元素位置

同上。只不过等于号加在另一个条件中。

//A为递增数列，x为欲查询的数，函数返回查找到的索引，未查找到返回-1
int binarySearch(int a[],int low,int high,int x){
    while (low <= high){
        int mid = low + (high - low) / 2;
        if (a[mid] <= x){
            low = mid + 1;
        }
        else if (a[mid] > x){
            high = mid - 1;
        }
    }
    return low;
}

与上面唯一的不同在于将等号放在了条件if (a[mid] <= x)中，但是却将最终结果变成了查找第一个大于x的元素位置。

分析：

此时，对于小于等于x的情况，都是在右半部分查找（提高low），该条件会导致低位low不断向右靠近，直到最后一个小于或等于x的位置。

当（low==high）时，将low = mid+1，最终将返回第一个大于x的位置索引。

解决

二分法解决

有了以上二分法的基础，那么这道题目可以总结为，查找最大的小于等于mp的数，这个问题可以转为上面的查找第一个大于mp的元素位置 - 1就得到了最大的小于等于x的数位置。

*注意： *的范围虽然不超过int范围，但是mp的范围是可能溢出的，所以这里选用long long作为数据类型。

/*
 * app=PAT-Basic lang=c++
 * https://pintia.cn/problem-sets/994805260223102976/problems/994805291311284224
 */
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int a[maxn] = {};
int N, p;
/* 二分法：
 * 注意数据边界，10^9很容易超过int范围，所以用long long
 */
int binarySearch(int low,long long m){
    int high = N - 1;
    while (low <= high){
        int mid = low + (high - low) / 2;
        if (a[mid] <= m*p)
            low = mid + 1;
        else
            high = mid - 1;
    }
    return low;
}
int main()
{
    scanf("%d%d", &N, &p);
    for (int i = 0; i < N; i++){
        scanf("%d",&a[i]);
    }
    sort(a,a+N);
    int maxNum = 0;
    for (int i = 0; i < N; i++){
        int low = binarySearch(i, a[i]);
        maxNum = low - i > maxNum ? low - i : maxNum;
    }
    printf("%d",maxNum);
    return 0;
}

双指针法解决

使用双指针法时，有一个超时点，需要优化，因为是从i+1开始向后递增的，其实这个值不需要每次循环都重新赋值i+1，因为数组是递增的。所以，对于后面的数来说，a[high]要么是第一个大于mp的数，要么是小于等于mp的数。

/*
 * app=PAT-Basic lang=c++
 * https://pintia.cn/problem-sets/994805260223102976/problems/994805291311284224
 */
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;
int a[maxn] = {};
int main()
{
    /*双指针法*/
    int N, p;
    long long mp;
    scanf("%d%d",&N,&p);
    for (int i = 0; i < N;i++){
        scanf("%d", &a[i]);
    }
    sort(a, a + N);
    int max = 0,high = 0;//high赋值一次即可
    for (int i = 0; i < N;i++){
        mp = (long long)a[i] * p;
        while (high < N){
            if (a[high] <= mp) high++;//对于后面的数来说，a[high]要么是第一个大于mp的数，要么是小于等于mp的数。
            else break;
        }
        max = max > high - i? max : high - i;
    }
    printf("%d",max);
    return 0;
}