题解：P8088 『JROI-5』Autumn

Hello_Coding · 2025-05-01 23:16:44 · 题解

Solution

思路：二分答案。
问是哪来的？看看题，最小化最大值嘛！
不会有不会二分答案模板的吧？先上一个：

int l = 1, r = n, mid, ans;
while (l <= r) {
    mid = (l + r) >> 1;
    if (Check(mid)) {
        ans = mid;
        l = mid + 1; // 或 r = mid - 1
    } else r = mid - 1; // 或 l = mid + 1
}
cout << ans << '\n';

但是，这里我们要的是数组中的值，而非 1 至 n 间任意值，所以我们需要一点修改——

// num数组记录a数组中出现的数
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) num[++cnt] = a[i][j];
sort(num + 1, num + 1 + cnt);
cnt = unique(num + 1, num + 1 + cnt) - num;
// 进行二分
l = 1, r = cnt;
while (l <= r) {
    mid = (l + r) >> 1;
    if (Check(mid)) {
        ans = mid;
        r = mid - 1;
    } else l = mid + 1;
}
cout << num[ans] << '\n';

OKOK，我们现在要的就是 Check 函数了！
将每一个数列（记为 d）从大到小排序，则可将题转化为最小化 d[k] 的最大值。
由于从大到小排序后期用 STL 不太方便，所以我们选择从小到大排序，然后最小化 d[m - k + 1] 的最大值。
设在某一方案中，d[m - k + 1] 的最大值的最小值为 t。
如果该方案可行，则对于每一个 d，d[k] 及其之前的每一个数都应小于 t。
如果有大于的怎么办？我们有 x 次的交换机会，将别的数列中多余的小于 t 的值换到这个序列来，以多补少。
假如够换，OK；假如不够换，那么退而求其次，看别的方案能不能行。这不就是二分的思想吗？
上 Check 代码：

bool Check(int pos) {
    int t = num[pos], lt = 0, gt = 0;
    for (int i = 1; i <= n; i++) {
        int p = upper_bound(a[i] + 1, a[i] + 1 + m, t) - a[i]; // 要事先将每条数列排序
        if (k >= p) lt += k - p + 1;
        else gt += p - k - 1;
    }
    if (lt <= gt && lt <= x) return true;
    else return false;
}

那么，完整代码呈现一下：

#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int N = 2e3 + 5;
int n, m, k, x, a[N][N], l, r, mid, ans, num[N * N], cnt = 0;
bool Check(int pos) {
    int t = num[pos], lt = 0, gt = 0;
    for (int i = 1; i <= n; i++) {
        int p = upper_bound(a[i] + 1, a[i] + 1 + m, t) - a[i];
        if (k >= p) lt += k - p + 1;
        else gt += p - k - 1;
    }
    if (lt <= gt && lt <= x) return true;
    else return false;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) cin >> a[i][j], num[++cnt] = a[i][j];
        sort(a[i] + 1, a[i] + 1 + m);
    }
    sort(num + 1, num + 1 + cnt);
    cnt = unique(num + 1, num + 1 + cnt) - num;
    cin >> k >> x;
    k = m - k + 1;
    // max a[k]
    l = 1, r = cnt;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (Check(mid)) {
            ans = mid;
            r = mid - 1;
        } else l = mid + 1;
    }
    cout << num[ans] << '\n';
    return 0;
}