题目大意
给出一个 \(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;
}
标签:const,CF446B,格子,int,long,Modification,DZY,贪心
From: https://www.cnblogs.com/baijian0212/p/solution-cf446b.html