题目大意
给出一个 \(n \times m\) 的矩阵，并进行 \(k\) 次操作，每次操作将矩阵的一行或一列的所有元素的值减 \(p\)，得到的分数为这次修改之前这一列或一行的元素和，求分数最大值。
思路
先说一下假贪心为什么是错的。
有一个很显然的贪心思路，分别用两个堆分别维护行与列的和，每次在两个堆的堆顶选最大的。
这种思路显然是错误的，我们直接给出一个组 hack 数据：
2 6 6 1
1 1 1 1 1 1
1 1 1 1 1 1
如果采用假贪心会导致先选择两个行，答案为 \(8\)；但如果选择六列，答案为 \(18\)。
我们从每个格子的角度去考虑，假设我们已知这个格子被选了 \(x\) 次，那么它的贡献应当是 \(a+ a - p + a - 2p + \dots + a - (x - 1)p\)。我们发现贡献与这个格子是在行中被选中还是在列中被选中无关，那么我们就可以假设先操作所有的行，再操作所有的列。
我们还是把行和列分开贪心，记 \(ansLine_i\) 表示行选了 \(i\) 个的最大答案，\(ansRow_i\) 为列的，同理。
那么显然有
\[ans=\max_{i=0}^{k} \left\{ Line_i + Row_i-i\times p (k-i) \right\}
\]
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1255;
const int M = 1005000;
long long n,m,k,p;
long long a[N][N];
long long ans = LLONG_MIN + 114514;
priority_queue<long long> queLine,queRow;
// Sum of Line or Row
long long ansLine[M],ansRow[M];
int main() {
ios::sync_with_stdio(false);
cin >> n >> m >> k >> p;
for(int i = 1;i <= n; i++)
for(int j = 1;j <= m; j++)
cin >> a[i][j];
long long LineSum = 0;
for(int i = 1;i <= n; i++) {
LineSum = 0;
for(int j = 1;j <= m; j++)
LineSum += a[i][j];
queLine.push(LineSum);
}
long long RowSum = 0;
for(int i = 1;i <= m; i++) {
RowSum = 0;
for(int j = 1;j <= n; j++)
RowSum += a[j][i];
queRow.push(RowSum);
}
for(int i = 1;i <= k; i++) {
long long Line,Row;
Line = queLine.top();
Row = queRow.top();
queLine.pop();
queRow.pop();
ansLine[i] = ansLine[i - 1] + Line;
ansRow[i] = ansRow[i - 1] + Row;
queLine.push(Line - p * m);
queRow.push(Row - p * n);
}
for(int i = 0;i <= k; i++)
ans = max(ans,ansLine[i] + ansRow[k - i] - 1ll * i * (k - i) * p);
cout << ans << "\n";
return 0;
}