PAT 1085. Perfect Sequence (25)

Posted on Edited on In

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

方法：快速排序 + 二分查找 tips：M <= m * p 最好转化成 M / p <= m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdlib>
#include <cstdio>

int get(int *nums, double x, int l, int r) {
    int mid = (l + r) / 2;
    if (l >= r) return mid;
    if (nums[mid] < x) return get(nums, x, mid + 1, r);
    if (nums[mid] - x < 0.1) return mid;
    else return get(nums, x, l, mid);
}

int cmp(const void *a, const void *b) {
    int arg1 = *static_cast<const int *>(a);
    int arg2 = *static_cast<const int *>(b);

    if (arg1 > arg2) return 1;
    if (arg1 < arg2) return -1;
    return 0;
}

int main() {
    int n = 0, p = 0;
    scanf("%d %d", &n, &p);
    int *nums = new int[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
    }
    qsort(nums, n, sizeof(nums[0]), cmp);
    int cnt = 0;
    for (int i = n - 1; i >= 0; i--) {
        int j = get(nums, nums[i] * 1.0 / p, 0, i);
        cnt = i - j + 1 > cnt ? i - j + 1 : cnt;
    }
    printf("%d\n", cnt);
    delete[] nums;
    return 0;
}