PAT A1085 Perfect Sequence (25分)

前言

传送门

正文

参考题解

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
/* 完美序列 给定n个数，从这n个数中尽可能多选择一些数组成一个序列，使得 该序列的最大值不M大于该序列的最小值m的p倍。求选出的数的最大个数 问题的关键在于：能使选出的数个数最大的方案，一定是在该递增序列中选择连续的若干 个数的方案 思路： 首先将这些序列升序排序，因为n范围是10^5，故用双重循环遍历会超时，因此 考虑使用二分搜索。i做第一层循环，从位置0开始，对每一个数a[i]，在a[i+1]~a[n-1]之间 使用二分搜索找到第一个大于a[i]*p的数的位置j，这样对于j-i就是对于i来说满足a[j]<=a[i]*p 的最大长度，最后只需要取j-i的最大值即可 注意点: 1、由于p和每个数字范围都是10^9,因此数据类型采用long long类型 2、需要尤其注意若序列中的数都不超过a[i]*p ，则返回n */
typedef long long LL;
const int N=1e5+10;
LL n,a[N],p,mp;
//二分模板 ,也可以直接使用upper_bound()函数 
//函数upper_bound()返回的在前闭后开区间查找的关键字的上界，返回大于val的第一个元素位置
int bSearch(int l,int r){
	if(a[r]<=mp)return n;//注意该处为易错点，即序列中的数都不超过a[i]*p 
	while(l<r){
		int mid=l+r>>1;
		if(a[mid]>mp)r=mid;
		else l=mid+1;
	}
	return l;
}
int main(){
	scanf("%lld %lld",&n,&p);
	for(int i=0;i<n;i++)scanf("%lld",&a[i]);
	sort(a,a+n);
	int res=1;
	for(int i=0;i<n;i++){
		mp=a[i]*p;
		int j=bSearch(i+1,n-1);
		res=max(res,j-i);
	}
	printf("%d\n",res);
	return 0;
}