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

akakal · 2025-10-11 19:46:24 · 题解

签到题。

对每一行开一个 vector，遍历 p，把 p_i 的位置塞进对应行的 vector， k 次操作可以把最后 k 个移到最前，那么该行期望的最少操作次数就是从后往前第 k+1 个的下标。

需要注意的是特判一下 k\ge m，这种时候答案一定为 m，否则会数组越界。

#include <bits/stdc++.h>
// #define int long long
#define lint long long
#define endl '\n'
using namespace std;
const int N = 1e5+5;

int n,m,k;
int p[N];
vector<int> v[N];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    int T;
    cin >> T;
    while(T--){
        cin >> n >> m >> k;

        for(int i = 1; i <= n; i++)
            v[i].clear();

        for(int i = 1; i <= n*m; i++){
            cin >> p[i];
            v[p[i]/m+!!(p[i] % m)].push_back(i);
        }

        if(k >= m){
            cout << m << endl;
            continue;
        }

        int ans = n*m;
        for(int i = 1; i <= n; i++)
            ans = min(ans,max(v[i][m-k-1],m));
        cout << ans << endl;
    }
    return 0;
}