题解：P15819 [JOI 2015 Final] 舞会 / Ball

xyy_xxyy · 2026-11-11 14:47:34 · 题解

联考 T2，又没有写出来，又急哭了。

考虑二分这谁想得到最后的答案 mid，运用经典 trick 经典在哪将所有 a_i \geq mid 变为 1，其他的为 0。

那么我们便将这题转换成了这样一个问题：有一些固定或不固定的 0 和 1，求出是否存在一种排列使得通过每次取出前三个数再把它们的中位数放回队尾让最后的 x 为 1。

这个感觉不太好做，或许可以考虑这样的一个东西，假设我有一个已经排列好的长度为 9 的序列 a，形如这样：

我对它进行一次操作，就变成了这样：

（其中 m_1 为 a_1,a_2,a_3 的中位数）

再来一次：

（其中 m_2 为 a_4,a_5,a_6 的中位数）

再来一次：

（其中 m_3 为 a_7,a_8,a_9 的中位数）

最后一次就是 m_1,m_2,m_3 的中位数了。

你发现了什么？反正我什么也没有发现。

每一次进行的操作，都只跟队首的那三个数中最多的那个数（也就是中位数）有关，并且这个东西是无后效性的，这启示我们对这一个东西 dp。

想一个好计算答案的状态，定义 dp_i 为使得第 i 位为 1 花费的最少的自由 1 的数量。初始化比较简单，对于本来就是 1 的位置代价为 0，对于本来就是 0 的位置代价为无穷大，其他的空位置就是 1 了。

转移也是简单的，对于前面三个数 x,y,z，这一位的代价就是从这三个数中找到两个数使其为 1，那我肯定是那两个代价最小的就行了，所以 dp_i=dp_x+dp_y+dp_z - \min (dp_x,dp_y,dp_z)，令 p 为总自由 1 的个数，然后看最后的那个值是否 \le p 即可。

实现的话用个 deque 就好了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], t[N], n, m;
bool check(int mid) {
    deque<int> q;
    for (int i = 1; i <= n; i++) {
        if (t[i] >= mid) {
            q.push_back(0);
        } else if (t[i] == 0) {
            q.push_back(1);
        } else {
            q.push_back(INT_MAX);
        }
    }
    int res = 0;
    for (int i = m + 1; i <= n; i++) {
        if (a[i] >= mid) {
            res++;
        }
    }
    while (q.size() != 1) {
        int x = q.front();
        q.pop_front();
        int y = q.front();
        q.pop_front();
        int z = q.front();
        q.pop_front();
        q.push_back(x + y + z - max({x, y, z}));
    }
    return q.front() <= res;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    int T = 1;
    // cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 1; i <= m; i++) {
            cin >> a[i] >> b[i];
            t[b[i]] = a[i];
        }
        for (int i = m + 1; i <= n; i++) {
            cin >> a[i];
        }
        int l = 1, r = 1e9;
        // cout << check(6) << '\n';
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (check(mid)) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        cout << r;
    }
    return 0;
}