题解：CF1835B Lottery

· · 题解

可以发现与目标数最接近的 k 张票一定是连续的，如果我们知道 Bytek 选的数，就可以 O(\log n) 的求出目标数的范围。

但挨个去枚举 Bytek 选的数肯定会 TLE，于是我们充分发挥人类智慧，Bytek 选的数肯定离某个 a_i 很近，于是枚举每个 a_i 周围的几个数去尝试是否为答案即可。

但是你会被这种数据

5 1000 20
528 106 507 130 510

制裁，于是要枚举 Bytek 选的数是 0 或 m 的情况。

:::info[code]

#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace xmx {
    const int N = 1e6+5;
    int n, m, k;
    int a[N];
    inline int solve(int ax) {
        int lef = upper_bound(a + 1, a + n + 1, ax) - a - 1;
        int rig = lower_bound(a + 1, a + n + 1, ax) - a;
        int Lef;
        if (lef - k + 1 <= 0) Lef = 0;
        else Lef = (a[lef - k + 1] + 1 + ax + 1) / 2;
        int Rig;
        if (rig + k - 1 > n) Rig = m;
        else Rig = (a[rig + k - 1] - 1 + ax) / 2;
        return max(Rig - Lef + 1, 0ll);
    }
    signed main() {
        cin >> n >> m >> k;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        sort(a + 1, a + n + 1);
        int ans = solve(m), ax;
        int id = m;
        ax = solve(0);
        if (ans < ax) {
            ans = ax;
            id = 0;
        } else if (ans == ax) {
            id = min(id, (int)0);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = -2; j <= 2; j++) {
                if (a[i] + j < 0 || a[i] + j > m)continue;
                ax = solve(a[i] + j);
                if (ans < ax) {
                    ans = ax;
                    id = a[i] + j;
                } else if (ans == ax) {
                    id = min(id, a[i] + j);
                }
            }
        }
        cout << ans << " " << id << "\n";
        return 0;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    xmx::main();
    return 0;
}
/*
范围[i,j]为优秀时x的范围max(x-a_i,a_j-x)<min(x-a_{i-1},a_{j+1}-x)
*/

:::