题目描述

blablabla

算法1

(暴力枚举) $O(n^2)$

算法2

(二分) $O(nlogn*logn或nlogn)$

考虑单调性，设答案为x，所有[HTML_REMOVED]=x均获胜，可用二分求解。
二分1：对每次二分的内容进行排序再逐个搜索，nlognlogn;
二分2：使用计数排序,nlogn

C++ 代码

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
const int N = 100010;
int n, m, k;
int h[N],cnt[N],s[N];
int i, j;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin >> n >> m >> k;
    for (i = 1; i <= n; i++)cin >> h[i];
    int mid, l = 1, r = n;
    bool flag = 0;
    for (i = 1; i <=n; i++)cnt[h[i]]++;
    for (i = 1; i <= 100000; i++)s[i] = s[i - 1] + cnt[i];
    for (i = k + 1; i <= 100000; i++)
        if (s[i] - s[i - k - 1] >= m)flag = 1;
    if (flag == 0) { cout << "impossible"; return 0; }
    while (l < r)
    {
        bool flag = 0;
        memset(cnt, 0, sizeof cnt);
        mid = l + r >> 1;
        for (i = 1; i <= mid; i++)cnt[h[i]]++;
        for (i = 1; i <= 100000; i++)s[i] = s[i - 1] + cnt[i];
        for (i = k + 1; i <= 100000; i++)
            if (s[i] - s[i - k - 1] >= m)flag = 1;
        if (flag) r = mid;
        else l = mid + 1;
        if (flag == 0 && mid == n) { cout << "impossible"; return 0; }
    }

    cout << l;

    return 0;
}