PAT 1030 完美数列 （二分）

1030 完美数列 (25分)
使用binarySearch

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

int n,p;
int nums[100010];

int binarySearch(int i,long long x){
    if(nums[n-1]<=x)return n;
    int l=i+1,r=n-1,mid;
    while(l<r){
        mid=l+(r-l)/2;
        if(nums[mid]<=x)l=mid+1;
        else r=mid;
    }
    return l;
}

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

使用upper_bound（注意upper_bound怎么用（c++ reference））
lower_bound和upper_bound找的分别是：左闭[右开)

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

int nums[100010];

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