Codeforces 2021 C Those Who Are With Us

$\text{[Problem Discription]}$

给定一个 $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\le n\times m\le 1\times 10^5$，且所有数据的 $n\times m$ 的总和不超过 $2\times 10^5$。

$\text{[Analysis]}$

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

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

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

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

f(i,j)=cntri+cntcj−[ai,j=max⁡1≤i≤n,1≤j≤m{ai,j}]f(i,j)=\text{cntr}_{i}+\text{cntc}_{j}- \left [a_{i,j}=\max\limits_{1 \leq i \leq n, 1 \leq j \leq m} \{a_{i,j} \}\right ]f(i,j)=cntri​+cntcj​−[ai,j​=1≤i≤n,1≤j≤mmax​{ai,j​}]

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

$\text{Code}$

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;
}