题目描述

给定一组数，请找出尽可能多的数使得等式M <= m * P成立，其中M为找出的数中最大值，m为最小值。

样例

10 8
2 3 20 4 5 1 6 7 8 9

8

算法1

(二分) $O(nlg2)$

给序列排序之后，问题就变成了找一个最大的区间满足条件。对于每一个M，可以二分找到小m。

C++ 代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

long long arr[N], b[N]; //注意：使用int会卡一个点
int n, p;

int helper(int l, int r, long long target) { //二分模板
    int oldr = r;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (target <= b[mid]) r = mid;
        else l = mid + 1;
    }

    return oldr - l + 1;
}

int main() {

    scanf("%d%d", &n, &p);  
    for (int i = 0; i < n; ++ i) scanf("%lld", &arr[i]);

    sort(arr, arr + n);

    for (int i = 0; i < n; ++ i) b[i] = arr[i] * p;


//  //二分下界
    int res = -1;
    for (int i = 0; i < n; ++ i)
        res = max(res, helper(0, i, arr[i]));

    cout << res << endl; 
    return 0;
}