PAT A1085 Perfect Sequence (25 分)/B 1030 完美数列 (25 分)

PAT A1085 Perfect Sequence (25 分)/B 1030 完美数列 (25 分)

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 (≤10^ 5​​ ) is the number of integers in the sequence, and p (≤10^ 9​​ ) is the parameter. In the second line there are N positive integers, each is no greater than 10^ ​9​​ .

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

B 1030 完美数列 (25 分) 中文题目:
给定一个正整数数列,和正整数 p,设这个数列中的最大值是 M,最小值是 m,如果 M≤mp,则称这个数列是完美数列。

现在给定参数 p 和一些正整数,请你从中选择尽可能多的数构成一个完美数列。

输入格式:
输入第一行给出两个正整数 N 和 p,其中 N(≤10^ ​5​​ )是输入的正整数的个数,p(≤10^ 9​​ )是给定的参数。第二行给出 N 个正整数,每个数不超过 10^ ​9​​ 。

输出格式:
在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

输入样例:
10 8
2 3 20 4 5 1 6 7 8 9
输出样例:
8
以下是AC的代码:

#include<cstdio>
//二分法 
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 100100;
long long num[maxn]={0};
long long n,p;
bool cmpll(long long a,long long b){
	return a<b;
}
int findps(long long i,long long j){//从当前位置开始,找最大数字; 
	long long left=i,right=j,sta=num[i]*p;
	
	while(left<right){
		long long mid=(left+right)/2;
		if(sta <num[mid]) right=mid-1;
		else left=mid+1;
	}
	return left-i;
}
int main(void){
	scanf("%lld%lld",&n,&p);
	for(long long i=0;i<n;i++){
		scanf("%lld",&num[i]);
	}
	sort(num,num+n,cmpll);
	int maxnum=0;//最大数字; 
	for(long long i=0;i<n;i++){
		int number=findps(i,n);
		if(number>maxnum) maxnum=number; 
	}
	printf("%d",maxnum);
	return 0;
}

思路:
这道题如果直接暴力枚举会运行超时,时间复杂度是O(n^ 2),但是用 二分法和 two pointers 的方法都可以解决。以下是用 two pointers 方法的代码:

//two pointers
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 100100;
long long num[maxn]={0};
bool cmpn(long long a,long long b){
	return a<b;
}
int main(void){
	long long n,p;
	scanf("%lld%lld",&n,&p);
	for(long long i=0;i<n;i++){
		scanf("%lld",&num[i]);
	}
	sort(num,num+n,cmpn);
	long long i=0,j=0;
	long long count=0,maxnum=0;
	while(i<n&&j<n){
		count=0;//重置count; 
		while(j<n&&p*num[i]>=num[j]){
			j++;
		}//j右移;
		count=j-i; 
		if(count>maxnum) maxnum=count;
		while(i<=j&&p*num[i]<num[j]) i++;//i右移; 
	}
	printf("%lld",maxnum);
	return 0;
} 
上一篇:supplier接口


下一篇:刷题-Leetcode-416. 分割等和子集