38. CF-Orac and Medians

链接

官方题解有严谨的证明。这里只写个思路。

1. 显然 \(k\) 必须存在于原数组中
2. 只要有连续两个 \(k\)，就可以完成任务
3. 小的数容易同化大的数
4. 考虑相对于 \(k\) 的大小关系
5. \(k\) 的附近存在不小于它的数就可以了
6. 考虑间距，要让中位数变大，必须是 \(\ge k\) 的数多，\(\lt k\) 的数少的情况
7. 那么必须存在一对 \(\ge k\) 的数，它们的间距不超过 \(1\)

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& i : a) cin >> i;
    bool ok = false;
    for (auto& i : a) {
        ok |= (i == k);
        i = (i >= k);
    }
    if (!ok) {
        cout << "no\n";
        return;
    }
    ok = (n == 1);
    for (int i = 0; i + 1 < n; ++i) {
        if (a[i] && a[i + 1])
            ok = true;
    }
    for (int i = 0; i + 2 < n; ++i) {
        if (a[i] && a[i + 2])
            ok = true;
    }
    cout << (ok ? "yes\n" : "no\n");
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    double a = 3400, b = 127000;
    cout << a / b << endl;
}