JZTXT

PAT_A 1085 Perfect Sequence

发布时间 2023-10-20 10:33:38作者: 永无荒城

Given a sequence of positive integers and another positive integer p. The sequence is said to be a perfect sequence if M≤m×p where M and m are the maximum and minimum numbers in the sequence, respectively.

Now given a sequence and a parameter p, you are supposed to find from the sequence as many numbers as possible to form a perfect subsequence.

Input Specification:

Each input file contains one test case. For each case, the first line contains two positive integers N and p, where N (≤105) is the number of integers in the sequence, and p (≤109) is the parameter. In the second line there are N positive integers, each is no greater than 109.

Output Specification:

For each test case, print in one line the maximum number of integers that can be chosen to form a perfect subsequence.

Sample Input:

10 8
2 3 20 4 5 1 6 7 8 9

Sample Output:

8

总结

二分 #two_pointers 可以用二分、two pointers两种方法。

  1. 二分有两种做法：
    • 二分答案；
    • 对排序后的每一个a[i]，在a[i+1]~a[n-1]内查找第一个超过a[i]*p的数的位置j。
  2. two pointers：i=j=0，让j在符合条件的情况下不断增大，不能增大时则令i++，时间复杂度只需 $o(n)$ 。
// 二分答案
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,p, e[100000+5];
int main(){
	scanf("%lld%lld", &n, &p);
	for(int i = 0; i < n; i++) scanf("%lld", &e[i]);
	sort(e, e+n);
	int lo = 0, hi = n, mi=0;
	while(hi > lo){
		mi = (hi + lo)>>1;
		int en = 0;
		for(int i = 0; i + mi < n; i++){
			if(e[i + mi] <= e[i]*p){
				en = 1;
				break;
			}
		}
		if(en) lo = mi+1;
		else hi = mi;
	}
	printf("%d", mi+1);
	return 0;
}

//二分数组
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,p, e[100000+5];
int main(){
	scanf("%lld%lld", &n, &p);
	for(int i = 0; i < n; i++) scanf("%lld", &e[i]);
	sort(e, e+n);
	int r = 1;
	for(int i = 0; i < n; i++){
		int j = upper_bound(e+i+1, e+n, (ll)e[i]*p) - e;
		r = max(r, j-i);
	}
	printf("%d", r);
	return 0;
}

//two pointers
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,p, e[100000+5];
int main(){
	scanf("%lld%lld", &n, &p);
	for(int i = 0; i < n; i++) scanf("%lld", &e[i]);
	sort(e, e+n);
	int r = 0;
	int i = 0, j = 0;
	while(i < n && j < n){
		while(j < n && e[j] <= e[i]*p){
			r=max(r, j-i+1);
			j++;
		}
		i++;
	}
	printf("%d", r);
	return 0;
}