自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:48:32，当前版本为作者最后更新于2023-07-16 21:58:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道很好的大眼观察题。

对于每个元素 $a_{x,y}$，令 $s_{x,y}=\sum \limits _{i = 1}^n a_{i,y} + \sum \limits _{i = 1}^m a_{x,i}$；考虑每一次操作对 $s_{x,y}$ 与 $a_{x,y}$ 相对大小的影响。显然的一次操作会使 $s_{x,y}$ 减少 $n+m$，使 $a_{x,y}$ 减少 $1$，所以它们的相对大小 $s_{x,y}-a_{x,y}$ 会减少 $n+m-1$。

因为我们想让 $a_{x,y}\ge s_{x,y}$，即让 $s_{x,y}-a_{x,y}$ 尽快减到 $0$，所以需要的操作数即为 $\left\lceil\dfrac{s_{x,y}-a_{x,y}}{n+m-1}\right\rceil$。$s_{x,y}$ 很容易计算出，令 $r_x=\sum\limits_{i=1}^m a_{x,i}$，$c_y=\sum\limits_{i=1}^n a_{i,y}$，则 $s_{x,y}=r_x+c_y$，操作数 $\left\lceil\dfrac{s_{x,y}-a_{x,y}}{n+m-1}\right\rceil=\left\lceil\dfrac{r_x+c_y-a_{x,y}}{n+m-1}\right\rceil$。

最后考虑操作次数第 $k$ 小的数，它的操作数即为需要的操作数。找到 $k$ 小数可以使用 STL 的 std::nth_element() 函数。

时间复杂度 $O(nm)$，足以通过。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int div_ceil(int x,int y){
  return x/y+!!(x%y);
} // 整数除法向上取整函数
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,m,k; cin>>n>>m>>k;
  vector<vector<int> > a(n,vector<int>(m));
  for(auto &i:a)for(auto &j:i)cin>>j;
  vector<int> r(n),c(m),d;
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      r[i]+=a[i][j],c[j]+=a[i][j];
      // 预处理 r,c 数组
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      d.emplace_back(div_ceil(r[i]+c[j]-a[i][j],n+m-1));
      // 将所有操作数放进一个 std::vector
  nth_element(d.begin(),d.begin()+k-1,d.end());
  cout<<d[k-1]<<endl;
  // 找出 k 小数并输出
  return 0;
}