算法竞赛模板

2025CC福建邀请

中位数的一个trick 大于等于某个数设置为1，小于设置为0
这里需要二分选择某个数作为可能的最大值，然后尽可能减少0的数量，最终比较0和1的数量
发现只有000 和 00100这样的情况有可能减少0和1的数量差值，其他情况操作0和1的数量差值都不会改变
用栈维护

有一个地方 vector tmp; 放到for 循环里面直接tle了，放到外面然后用tmp.clear() 500ms
因为构造和销毁开销太大了

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
// #define LOCAL
#ifdef LOCAL
#define dbg(...) _((char*)#__VA_ARGS__,__VA_ARGS__)
template<typename t> void _(char* p, t x) { cout << p << '=' << x << '\n'; }
template<typename t, typename... a>
void _(char* p, t x, a... y) { while (*p != ',')cout << *p++;cout << '=' << x << ' ';_(p + 1, y...); }
#else
#define dbg(...) 0
#endif

vector<int> d = {1,0,0}, e = { 0,0,0 };

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<int> b = a;
    sort(b.begin() + 1, b.end());
    b.erase(unique(b.begin() + 1, b.end()), b.end());
    int cnt = b.size() - 1;
    int ans = 0;
    int L = 1, R = cnt;
    vector<int> c(n+1);
    auto ck = [&](int m) -> bool {
        for (int i = 1; i <= n; i++) {
            c[i] = a[i] >= b[m] ? 1 : 0;
        }
        stack<int> st;
        vector<int> tmp;
        for (int i = 1; i <= n; i++) {
            st.push(c[i]);
            tmp.clear();
            if (st.size() >= 3) {
                for (int j = 1; j <= 3; j++) {
                    tmp.push_back(st.top());
                    st.pop();
                }
                if (tmp == d || tmp == e) {
                    st.push(0);
                }
                else {
                    for (int j = 2; j >= 0; j--) st.push(tmp[j]);
                }
            }
        }
        int sum = 0;
        while (st.size()) {
            sum += st.top() == 1 ? 1 : -1;
            st.pop();
        }

        return sum >= 1;
        };
    while (L <= R) {
        int mid = L + R >> 1;
        dbg(mid);
        if (ck(mid)) {
            L = mid + 1;
            ans = max(ans, b[mid]);
        }
        else {
            R = mid - 1;
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--) solve();
    return 0;
}