专栏文章

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

ggreatest_show
P14197题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmsmp6
此快照首次捕获于
2025/12/02 04:58
3 个月前
此快照最后确认于
2025/12/02 04:58
3 个月前
查看原文

翻译

有一个 nn 行 mm 列的网格。网格中的单元格编号从 11 到 n×mn \times m，其中第 ii 行第 jj 列的单元格编号为 ((i−1)×m+j)((i−1)×m + j)。
给定一个长度为 n×mn×m 的排列 p1,p2,…,pnmp_1, p_2, …, p_{nm}（注：排列是指 11 到 n×mn \times m 的每个整数恰好出现一次的序列），我们将按照该排列执行 n×mn \times m 次操作。第 ii 次操作时，我们会标记单元格 pip_i。如果在第 bb 次操作后，至少存在一行的所有单元格都被标记，且 bb 是满足该条件的最小整数，那么我们称 bb 为该排列的 bingo 整数。
你可以对这个排列进行至多 kk 次修改（包括 00 次）。每次修改可交换排列中的一对元素。请计算修改后可能得到的最小 bingo 整数。

思考

首先得明确问题核心：通过最多 kk 次交换排列元素，让 最早有一行全被标记 的操作次数 bingo 整数 尽可能小。首先要理清两个关键对应 —— 一是根据单元格编号 ((i−1)×m+j)((i-1)×m+j) 反推出它所在的行，二是用“位”数组记录每个单元格在排列中的位置（也就是被标记的时间），某行全标记的时间其实就是该行所有单元格“位”值的最大值，因为得等最后一个单元格标记完该行才满。
没交换 k=0k=0 时，bingo 整数 就是所有行“位”最大值里的最小值，选最早全满的行就行。有交换的话，核心是用排列里“标记早”的小“位”值，替换目标行里“标记晚”的大“位”值，减小该行的“位”最大值。最多能换 s=min⁡(k,m)s=\min (k,m) 个，因为行只有 mm 个单元格，换超 mm 个没必要，具体是把目标行的“位”排序后，去掉最大的 ss 个，换成整个排列里最小的 ss 个“位”值，此时该行新“位”集合的最大值就是优化后的全标记时间。最后算所有行这样优化后的“位”最大值，取最小的那个，就是最终的最小 bingo 整数

Code:

CPP
#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;//好习惯++
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...