[入门赛 #14] 魔法少女扶苏 (Hard Version) 题解

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