仓库货物调配问题 tag 贪心，枚举，数据结构 题意简述 给定一个 $n \times m$ 的矩阵，每次操作可以选择一列或者一行，将这一列数的和计入收益，然后将这一列数全部减少 $p$。求操作 $k$ 次的最大收益。 fun fact 赛时看到这个题的时候，注意到每次取行和列都互相不影响（应该说，假设取走某一行后，相当于再每一列都取走了一个固定的 $p$，不影响每一列和的相对大小）。所以想到一个贪心策略：每次取和最大的行或者列。这样很容易实现，利用2个优先队列维护行和列的和，每次去除两个对头比较，取较大的取出，取出后（假设取出的是行），将他减去 $m \times p$ 后再加入优先队列，然后再给列的tag加上 $p$(表示给所有列都减去了一个 $p$)，这样就可以保证每次取的都是当前最大的行或者列。 事实上，这个思路是错误的，或者说不好处理这种情况：存在行最大值和列最大值相同的情况。比如样例： ``` input1: 3 3 2 4 5 4 3 5 4 4 1 2 6 ans1: 25 input2: 3 3 2 4 5 5 1 4 4 2 3 4 6 ans2: 25 ``` 在第一个样例中应该先取行，而第二个中应该先取列。 题解思路 回到正确的思路，我们还是有结论：取行和列互不影响。我们错误的贪心在于无法处理行和列相等时，应该先取行还是先取列。我们跳过这个问题，既然行和列互不影响，我们考虑答案的结构：答案一定是取 $x$ 次行最大和 $y$ 次列最大。那么很显然，$x$ 和 $y$ 是我们可以枚举的，而取 $x$ 次行最大和 $y$ 次列最大，这是我们可以先行预处理出来的，再做前缀和即可。然后枚举 $x$，那么 $y = k - x$，每次的答案就是 $f(x) = pre_{row_x} + pre_{col_{k-x}}$。但是，我们还需要考虑行和列会有交叉操作：假设我们取了 $x$ 次行，那么每一列的值都应该相应的减少 $x \times p$，所以我们取 $k - x$ 次列时，这一部分是多计算的（也就是把 $x \times p$ 多算了 $k - x$ 次）。所以最后的答案应该减掉 $x \times p \times (k - x)$，那么最后的答案应该是: $$ ans = \max_{i=0}^k (pre_{row_i} + pre_{col_{k-i}} - i \times p \times (i - p)) $$ tips：$-\inf$ 要开到 $-1e18$。 参考代码 ```cpp #define matrix(_x, _y, _z) vector<vector<int>>(_x, vector<int>(_y, _z)) #define debug(_x) cout << #_x << '=' << _x << endl using i64 = long long; using i128 = __int128; using pii = pair<int, int>; using mat = vector<vector<int>>; using u64 = unsigned long long; constexpr int N = 2e5 + 10; // dont use umap!!! signed main() { IOS; int n,m,k,p; cin >> n >> m >> k >> p; auto g = matrix(n + 1, m + 1, 0); for(int i = 1; i <= n; i ++) for(int j = 1; j <= m; j ++) cin >> g[i][j]; priority_queue<int> heaprow, heapcol; for(int i = 1; i <= n; i ++) // row { int sum = 0; for(int j = 1; j <= m; j ++) { sum += g[i][j]; } heaprow.push(sum); } for(int i = 1; i <= m; i ++) // col { int sum = 0; for(int j = 1; j <= n; j ++) { sum += g[j][i]; } heapcol.push(sum); } i64 ans = -1e18; vector<int> precol(k + 1), prerow(k + 1); for(int i = 1; i <= k; i ++) { auto colsum = heapcol.top(); auto rowsum = heaprow.top(); heapcol.pop(); heaprow.pop(); precol[i] = precol[i - 1] + colsum; prerow[i] = prerow[i - 1] + rowsum; heapcol.push(colsum - n * p); heaprow.push(rowsum - m * p); } for(int i = 0; i <= k; i ++) { ans = max(ans, prerow[i] + precol[k - i] - i * (k - i) * p); } cout << ans << '\n'; return 0; } ```