PAT A1085 Perfect Sequence

题目链接

手动实现二分法

解题思路

手动实现二分法，找出从[i+1,n-1]中大于nums[i]*p的第一个数。注意当x小于mid时，大于x的数也包括mid。

代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
ll nums[maxn],p;
int n;

int binaSearch(int i, ll x){
    if(x>=nums[n-1]) return n;//所有数都不大于x，返回n
    int l=i+1,r=n-1,mid;//在[i+1,n-1]内查找
    while(l<r){
        mid=(l+r)/2;
        if(nums[mid]<=x){//如果中间值小于等于x，说明比x大的数在mid右边
            l=mid+1;
        }else{//如果nums[mid]>x说明第一个大于x的数在mid之前（含mid）
            r=mid;
        }
    }
    return l;
}

int main() {
    scanf("%d%lld",&n,&p);
    for(int i=0;i<n;i++){
        scanf("%lld",&nums[i]);
    }
    sort(nums,nums+n);
    int cnt=0;
    for(int i=0;i<n;i++){
        int j=binaSearch(i,nums[i]*p);
        cnt=max(cnt,j-i);
    }
    printf("%d",cnt);
    return 0;
}

使用upper_bound函数实现二分法

upper_bound函数返回递增排序好的数列中第一个大于x的数的位置

lower_bound函数返回递增排序好的数列中第一个大于等于x的数的位置

代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
ll nums[maxn],p;
int n;

int main() {
    scanf("%d%lld",&n,&p);
    for(int i=0;i<n;i++){
        scanf("%lld",&nums[i]);
    }
    sort(nums,nums+n);
    int cnt=0;
    for(int i=0;i<n;i++){
        int j=upper_bound(nums+i+1,nums+n,nums[i]*p)-nums;
        cnt=max(cnt,j-i);
    }
    printf("%d",cnt);
    return 0;
}