A1085 Perfect Sequence [二分、two pointers]

题目大题：找出最长子序列，且最大的数不能超过最小的数p倍
思路：
1.因为是求二分查找的最后一个值，所以等价于排序后二分查找不满足条件的第一个位置
2. 注意点：注意每次查找可能有没有不满足条件的数字出现，所以要提前判断一下

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
long long int a[100001];
int main()
{
	int n; long long int p;
	cin >> n >> p;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a + n); int inf = -1;
	for (int i = 0; i < n; i++)
	{
		if (a[n - 1] <= (a[i] * p))
		{
			if ((n - i) > inf)
				inf = n - i;
		}
		else
		{
			long long int temp = a[i];
			int left = i+1, right = n - 1;
			while (left < right)
			{
				int mid = (left + right) / 2;
				if (a[i] * p < a[mid])
					right = mid;
				else
					left = mid + 1;
			}
			if ((right - i) > inf)
				inf = right - i;
		}
	}
	cout << inf << endl;
}

#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<time.h>
using namespace std;
int main()
{
	int n, m; int a[100001];
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}
	sort(a, a + n);
	int i = 0, j = 0, count = 1;
	while (i < n && j < n)
	{
		while (j < n && a[j] <= (long long)a[i] * m)
		{
			count = max(count, j - i + 1);
			j++;
		}
		i++;
	}
	cout << count << endl;
	return 0;
}