1085 Perfect Sequence (25 分)
Given a sequence of positive integers and another positive integer p. The sequence is said to be a perfect sequence if M≤m×p where M and m are the maximum and minimum numbers in the sequence, respectively.
Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.
Input Specification:
Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (≤10?5??) is the number of integers in the sequence, and p (≤10?9??) is the parameter. In the second line there are N positive integers, each is no greater than 10?9??.
Output Specification:
For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.
Sample Input:
10 8
2 3 20 4 5 1 6 7 8 9
Sample Output:
8
还熟悉二分的写法就很简单，不要怕，暴力基础上做一点优化即可。 若记得api upper_bound就更简单了
手写：
#include<bits/stdc++.h>
using namespace std;
long long N,p,a[100010];//返回数组a中第一个大于x的元素的下标
int Upper_bound(int i,long long x){if(a[N-1]<=x) return N;//都小于 返回最大下标+1 含义是x应该插入的位置int left=i+1,right=N-1;//p至少为1 也即a[i]<=x=a[i]*p恒成立 所以从i+1开始算起 while(left<right){int mid=(left+right)/2;if(a[mid]>x){right=mid;}else{//a[mid]<=xleft=mid+1;//一点都不要多余 小于等于x时才+1 一步一步尝试，最终定是第一个大于x的位置}} return left;
}int main(){//freopen("in.txt","r",stdin);cin>>N>>p;for(int i=0;i<N;i++) cin>>a[i];sort(a,a+N);int ans=0;for(int i=0;i<N;i++){int j=Upper_bound(i,a[i]*p);ans=max(ans,j-i); }cout<<ans;return 0;
}
API:
#include<bits/stdc++.h>
using namespace std;
long long N,p,a[100010];
int main(){//freopen("in.txt","r",stdin);cin>>N>>p;for(int i=0;i<N;i++) cin>>a[i];sort(a,a+N);int ans=0;for(int i=0;i<N;i++){int j=upper_bound(a+i,a+N,a[i]*p)-a;//-a才是下标 a+i+1开始最好 ans=max(ans,j-i);}cout<<ans;return 0;
}
思路没错，分析得也对，a[i]*p->a[j] a[j]是第一个大于p*a[i]的数(中间都小于等于) j-i就是答案
直接二重循环肯定超时，10^5*10^5
二分的话可以 n*logn=5*10^5 不会超时
二分其实也很简单，每次寻找a[j]的代码换用二分法查找即可
记住upper_bound(a,a+n,val) a[0~n-1]范围内(其实是[a,a+n)) 第一个大于val的位置指针 返回值-a就是下标lower_bound(a,a+n,val) 同上，不过找的是第一个大于等于val的位置，返回值后面可能有等于val的，但没有大于val的
two pointer做法 也很妙，每次保证i,j的距离最大 j能加就j++。i不到万不得已不i++ 时间复杂度O(N)更短
#include<bits/stdc++.h>
using namespace std;long long N,p,a[100010];int main(){
// freopen("in.txt","r",stdin);cin>>N>>p;for(int i=0;i<N;i++) scanf("%d",&a[i]);sort(a,a+N);int i=0,j=0,count=0;while(i<N&&j<N){//O(N) if(a[j]<=a[i]*p){count=max(count,j-i+1);j++;//j疯狂加 最终j先到N 结束 }else{i++;//i不到万不得已不加 }}cout<<count;return 0;
}