526互联

1085 Perfect Sequence（附测试点5分析）

发布时间 2023-06-08 09:49:44作者: Yohoc

题目：

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

思路：

将所给数列进行排序，然后从大到小遍历序列，每次遍历（遍历最大值a[i]）都在序列中找出大于等于a[i]/p 的数（最小值）的下标，然后计算子序列的大小。

注意测试点5答案错误是因为数列没有使用long long 类型来存储，同时也要注意 a[i] * p 会超出int的范围

使用了二分查找的思想，二分查找求第一个大于等于某个值x的元素的位置的代码如下：

int upper_bound(int A[], int left, int right, int x){
    int mid;
    while(left < right){
        mid = (left + right) / 2;
        if(A[mid] > x){
            right = mid;
        }else{
            left = mid + 1;
        }
    }
    return left;
}

 

 

代码：（满分）

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int p;
long long a[100005];
int find(int left, int right, long long x){
    while(left < right){
        int mid = (left + right) / 2;
        long long ll = a[mid] * p;
        if(ll >= x){
            right = mid;
        }else{
            left = mid + 1;
        }
    }
    return left;
}
int main(){
    int n;
    scanf("%d%d", &n, &p);
    for(int i = 0; i < n; i++){
        scanf("%lld", &a[i]);
    }
    sort(a, a + n);
    int maxx = -1;
    for(int i = n - 1; i >= 0; i--){
        int index = find(0, i, a[i]);
        if(i - index + 1 > maxx) maxx = i - index + 1;
    }
    cout<<maxx;
    return 0;
}