题目

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最大

解题思路

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

易错点

1. p(<=10^9)，所以m*p有可能超过int范围，数组元素类型需为long long，否则第5个测试点错误
2. 取第一个大于mp的数字下标-1，而不是第一个大于等于mp的数字下标（因为大于的情况下要-1，等于的情况下不需要-1，处理麻烦）

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;
}

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

原文：https://www.cnblogs.com/houzm/p/12252624.html