OIer的题解：P14197 [ICPC 2024 Hangzhou R] Kind of Bingo

· · 题解

翻译

有一个 n 行 m 列的网格。网格中的单元格编号从 1 到 n \times m，其中第 i 行第 j 列的单元格编号为 ((i−1)×m + j)。

给定一个长度为 n×m 的排列 p_1, p_2, …, p_{nm}（注：排列是指 1 到 n \times m 的每个整数恰好出现一次的序列），我们将按照该排列执行 n \times m 次操作。第 i 次操作时，我们会标记单元格 p_i。如果在第 b 次操作后，至少存在一行的所有单元格都被标记，且 b 是满足该条件的最小整数，那么我们称 b 为该排列的 bingo 整数。

你可以对这个排列进行至多 k 次修改（包括 0 次）。每次修改可交换排列中的一对元素。请计算修改后可能得到的最小 bingo 整数。

思考

首先得明确问题核心：通过最多 k 次交换排列元素，让 最早有一行全被标记 的操作次数 bingo 整数 尽可能小。首先要理清两个关键对应 —— 一是根据单元格编号 ((i-1)×m+j) 反推出它所在的行，二是用“位”数组记录每个单元格在排列中的位置（也就是被标记的时间），某行全标记的时间其实就是该行所有单元格“位”值的最大值，因为得等最后一个单元格标记完该行才满。

没交换 k=0 时，bingo 整数 就是所有行“位”最大值里的最小值，选最早全满的行就行。有交换的话，核心是用排列里“标记早”的小“位”值，替换目标行里“标记晚”的大“位”值，减小该行的“位”最大值。最多能换 s=\min (k,m) 个，因为行只有 m 个单元格，换超 m 个没必要，具体是把目标行的“位”排序后，去掉最大的 s 个，换成整个排列里最小的 s 个“位”值，此时该行新“位”集合的最大值就是优化后的全标记时间。最后算所有行这样优化后的“位”最大值，取最小的那个，就是最终的最小 bingo 整数

Code:

#include <bits/stdc++.h>
using namespace std;
//greatest_show 水印
int n, m, k, t;
int p[114514];
int r[114514];
int a[114514];
int greatest_show() {
    int b = 2e9; // 最小bingo值
    for (int i = 1; i <= n; i++) {// 收集行位置
        for (int j = 1; j <= m; j++) {
            int c = i * m + j;  // 单元格编号
            r[j - 1] = p[c];
        }
        sort(r, r + m);
        int s = min(k, m);
        int b1;  // 行最大位置
        if (s == 0) {
            b1 = r[m - 1];
        } else {
            int p1 = 0;
            if (m > s) {
                p1 = r[m - s - 1];
            }
            int p2 = a[s - 1];
            if (p1 > p2) {
                b1 = p1;
            } else {
                b1 = p2;
            }
        }
        if (b1 < b) {
            b = b1;
        }
    }
    printf("%d\n", b);
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d", &n, &m, &k);
        t = n * m;
        for (int i = 1; i <= t; i++) {// 记录单元格位置
            int c;
            scanf("%d", &c);
            p[c] = i;
        }
        for (int c = 1; c <= t; c++) {// 收集位置排序
            a[c - 1] = p[c];
        }
        sort(a, a + t); 
        greatest_show();
    }
    return 0;//好习惯++
}