PAT二分查找---1030 完美数列 (25分)

1030 完美数列 (25分)
二分查找常用函数:

  • lower_bound() 函数用于在指定区域内查找不小于目标值的第一个元素

  • upper_bound() 函数定义在头文件中,用于在指定范围内查找大于目标值的第一个元素

  • 第一次写的代码,测试点4没过

  • 下面举个例子,如数组:1,2,3,4,5,6,7,8,10,20
    如果 p= 2,取M=10,那么显然从10开始才符合条件,结果为2。但是可以很明显的发现:4,5,6,7,8 这一组数便满足条件,此时答案输出为5
    引用天上的人我是谁的博客文字

#include<iostream>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<sstream>
#include<string>
#include<cstdio>
#include<algorithm>
const int maxn=100005;
typedef long long ll;
using namespace std;

ll a[maxn];
int cnt=0;
int main() {
	int n,p;cin>>n>>p;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	ll maxx=a[n-1];
	for(int i=0;i<n;i++){
		if(a[i]*p>=maxx){
			cnt=i;
			break;
		}
	}
	cout<<n-cnt;
	return 0;
}

  • 看算法笔记代码用二分查找,不然超时
#include<iostream>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<sstream>
#include<string>
#include<cstdio>
#include<algorithm>

const int maxn=100005;
typedef long long ll;
using namespace std;

int a[maxn];

int main() {
	int n,p;cin>>n>>p;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	int ans=1;
	for(int i=0;i<n;i++){
		//在a[i+1]-a[n-1]中查找第一个超过a[i]*p的数,返回其位置给j
		int j=upper_bound(a+i+1,a+n,(ll)a[i]*p)-a;
		ans=max(ans,j-i); 
	}
	cout<<ans;
	return 0;
}


上一篇:2019 年十大热门 BT 站


下一篇:github ip列表