1030 完美数列/A1085 Perfect Sequence

idea

solution1(测试点5不通过)

直观想法是通过调整区间左右边界，找到改最大区间。但是这假定了左右区间的维护是可以对称维护的，显然不成立。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int main(){
	int n, p, l = 0, r, flag = 0;
	scanf("%d%d", &n, &p);
	for(int i = 0; i < n; i++){
		scanf("%d", a + i);
	}
	sort(a, a + n);
	r = n - 1;
	while(a[r] > a[l] * p){
		if(a[r - 1] <= a[l] * p) r--;
		else if(a[r] <= a[l + 1] * p) l++;
		else if(flag % 2 == 1) r--;
		else l++;
		flag++;
	}
	printf("%d", r - l + 1);
	return 0;
} 

solution2

还是要依次求对于以a[i]为开头的序列长度，判断位置是可以借助upper_bound()函数，即找到首个大于mp的元素位置pos后，右边界为pos - 1。找到首个大于mp的元素j，则想要找的区间为i到j - 1，长度为j - 1 - i + 1 = j - i。
注意，p范围10⁹，a[i]范围10⁹，乘积可能会超出int型范围，需要用long long型存。

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 1e5 + 10;
int a[maxn];
int main(){
	int n, p, ans = 1, r;//最大长度至少为1，即至少含一个数 
	scanf("%d%d", &n, &p);
	for(int i = 0; i < n; i++){
		scanf("%d", a + i);
	}
	sort(a, a + n);
	for(int i = 0; i < n; i++){
		r = upper_bound(a + i, a + n, (long long)a[i] * p) - a;
		ans = max(ans, r - i);
	}
	printf("%d", ans);
	return 0;
}