1030 完美数列 (25 分)

题目

题目链接

题解

思维。

从小到大排序后，从左开始选取一个数作为 m m m，二分选取右边的数作为 M M M，时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)；注意开long long！

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long LL;
LL p, a[N]; // 注意开 LL 
int n, ans;

int erfen (int l, int r, LL m) {
	while (l < r) {
		int mid = l + r + 1 >> 1;
		if (a[mid] <= m * p) l = mid;
		else r = mid - 1;
	}
	return l;
}

int main()
{
	cin >> n >> p;
	for (int i = 0;i < n;i ++) cin >> a[i];
	sort (a, a+n);
	
	for (int i = 0;i < n;i ++) {
		int x = erfen (i, n-1, a[i]);
		ans = max (ans, x - i + 1);
	}

	cout << ans << endl;
	return 0;
}