题解：CF2121C Those Who Are With Us

HPXXZYY · 2025-07-04 16:21:32 · 题解

给定一个 n \times m 的表格 a_{i,j}，你可以恰好进行一次如下操作：

1. 选择一个格点 (r,c)。
2. 对于所有满足 i=r 或者 j=c 的格点 (i,j)，使 a_{i,j} \leftarrow a_{i,j}-1。

求操作后所有格点最大值最小可能为多少。

多组数据，满足 1 \leq n \times m \leq 1 \times 10^{5}，且所有数据的 n \times m 的总和不超过 2 \times 10^{5}。

记原来矩阵的最大值为 t，显然由于只能进行一次操作，且一次操作最多让一个格点的值减小 1，所以最终答案要么是 t，要么是 (t-1)。

思考哪些情况会让答案为 (t-1)。

显然，当所有取得最大值的格点要么分布在第 r 行要么分布在第 c 列时，我们可以通过一次操作 (r,c) 把所有最大值都干掉；否则答案为 t 不变。

统计每一行每一列有多少个最大值，分别记为 \text{cntr}_{i},\text{cntc}_{j}，显然第 i 行和第 j 列的最大值的个数即为：

显然预先统计出最大值的个数 \text{cnt}，如果某个格点 (i,j) 满足 f(i,j)=\text{cnt}，那么这个 (i,j) 就是我们需要的格点。

const int N=1e5+100;

int OneZDoubleY(){
    int n=read(),m=read();
    vector<int> a[n+2];
    for(int i=1;i<=n;i++){
        a[i].push_back(0);
        for(int j=1;j<=m;j++)
            a[i].push_back(read());
    }

    int maxn=a[1][1];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            ckmax(maxn,a[i][j]);

    int cnt=0;
    vector<int> cntr(n+1),cntc(m+1);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if (a[i][j]==maxn){
                ++cntr[i];
                ++cntc[j];
                ++cnt;
            }

    bool flag=false;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            int t=cntr[i]+cntc[j];
            if (a[i][j]==maxn) t--;

            if (t==cnt){
                flag=true;
                break;
            }
        }

    return printf("%d\n",flag?maxn-1:maxn);
}
//大家可以挑战一下不用 vector，用 malloc 来处理

int main(){
    int T=read();
    while (T--) OneZDoubleY();

    return 0;
}