题目

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

题目分析

已知正整数序列seq[N]，最大值为M，最小值为m，已知另一个正整数p(<=10^9)，从数列中抽出一部分数字，求可以满足M<=m*p的数字最多抽取个数

要满足M<=mp抽取的数字最多（即：M与m中间夹的数字最多），需要取所有满足M<=mp的情况中，m最小，M最大

解题思路

思路 01（最优、二分查找、查找M复杂度O(logn)）

对seq[N]升序排序
依次遍历seq[i]，在i+1到N之间，找到最大满足M<=mp的数字（即：第一个满足大于mp的数字下标j-1）

思路 02 （two pointer、查找M复杂度O(n)）

对seq[N]升序排序
依次遍历seq[i]，j初始为0，开始从上次j往后找（因为i+1后m增大，m*q>=M，所以M增大，j只能在上次j之后）

易错点

p(<=10^9)，所以m*p有可能超过int范围，数组元素类型需为long long，否则第5个测试点错误
取第一个大于mp的数字下标-1，而不是第一个大于等于mp的数字下标（因为大于的情况下要-1，等于的情况下不需要-1，处理麻烦）
思路02中，只能从前往后找第一个不满足条件m*q>=M的，不能从后往前找最后一个满足条件的（测试点4超时）

Code

Code 01

#include <iostream>

#include <algorithm>

using namespace std;

int main(int argc,char * argv[]) {

	int n,p;

	scanf("%d %d",&n,&p);

	long long seq[n]= {0}; // 若为int，第5个测试点错误

	for(int i=0; i<n; i++) {

		scanf("%d",&seq[i]);

	}

	sort(seq,seq+n);

	int maxnum=0;

	for(int i=0; i<n; i++) {

		// 二分查找

		int left=i+1,right=n;

		int mid = left+((right-left)>>1);

		while(left<right) {

			mid = left+((right-left)>>1);

			if(seq[mid]>seq[i]*p) { //若是求第一个大于等于seq[i]*p，测试点2错误

				right=mid;

			} else {

				left=mid+1;

			}

		}

		if(right-i>maxnum)maxnum=right-i;

	}

	printf("%d",maxnum);

	return 0;

}

Code 01

#include <iostream>

#include <algorithm>

#include <cmath>

using namespace std;

int main(int argc,char * argv[]) {

	int n,p;

	scanf("%d %d",&n,&p);

	long long seq[n]= {0}; // 若为int，第5个测试点错误

	for(int i=0; i<n; i++) {

		scanf("%d",&seq[i]);

	}

	sort(seq,seq+n);

	// 写法一：

	int maxnum=0,j = 0;

	for(int i=0; i<n; i++) {

		while(j<n&&seq[i]*p>=seq[j]) j++;

		maxnum=max(maxnum,j-i);

	}

	// 写法二：

//	int i=0,j=0,maxnum=1;

//	while(i<n&&j<n) {

//		while(j<n&&seq[j]<=(long long)seq[i]*p) {

//			maxnum=max(maxnum,j-i+1);

//			j++;

//		}

//		i++;

//	}

	/*

		使用下面代码，第四个测试点超时

		j从后往前找最后一个满足条件的，测试点4超时

	*/

//	int maxnum=0,prej=0; //prej用于记录上次j的位置，之后的j只可能比prej大，m*p>=M；i+1因为m增大了，所以M一定增大

//	for(int i=0; i<n; i++) {

//		int j = n-1;

//		while(prej<=j&&seq[i]*p<seq[j]) j--;

//		maxnum=max(maxnum,j-i+1);

//		prej=j;

//	}

	printf("%d",maxnum);

	return 0;

}

巴特西

PAT Advanced 1085 Perfect Sequence (25) [⼆分，two pointers]

题目

题目分析

解题思路

思路 01（最优、二分查找、查找M复杂度O(logn)）

思路 02 （two pointer、查找M复杂度O(n)）

易错点

Code

Code 01

Code 01

最新文章

热门文章