明确题目的核心是要找到 找到第一个满足 M > m*p 的M的下标。然后用该下标减去起点的下标即为序列元素个数。
二分区间应当是M所有可能的取值范围。起点是i+1,终点是N而不是N-1,虽然A[N]上无元素。注意啊,原题要找的M是小于等于m*p的,所以这里的M可以是不存在的(返回M应该在的位置)。
注意点:
1. m*p可能溢出,最好改成M*1.0/p > m。
2. 要对元素个数为1或2的情况特判。
AC
#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>using namespace std;typedef long long LL;const int maxn = 100010;
//const LL SUP = (1LL<<63)-1;
int A[maxn];
int N,p;int BS(int m,int l,int r){int mid;while(l<r){mid = (l+r)/2;if(m<A[mid]*1.0/p){r = mid;}else{l = mid+1;}}return r;
}int main(){ cin>>N>>p;for(int i=0;i<N;i++){cin>>A[i];}sort(A,A+N);if(N==1){printf("1");return 0;}if(N==2){if(A[0]>=A[1]*1.0/p)printf("1");else printf("2");return 0;}int ans = 0; //找到第一个满足 M > m*p 的M for(int i=0;i<N-2;i++){int num = BS(A[i],i+1,N) - i;ans = max(ans,num);}printf("%d",ans);return 0;
}