1 条题解
-
1
仓库货物调配问题
tag
贪心,枚举,数据结构
题意简述
给定一个 的矩阵,每次操作可以选择一列或者一行,将这一列数的和计入收益,然后将这一列数全部减少 。求操作 次的最大收益。
fun fact
赛时看到这个题的时候,注意到每次取行和列都互相不影响(应该说,假设取走某一行后,相当于再每一列都取走了一个固定的 ,不影响每一列和的相对大小)。所以想到一个贪心策略:每次取和最大的行或者列。这样很容易实现,利用2个优先队列维护行和列的和,每次去除两个对头比较,取较大的取出,取出后(假设取出的是行),将他减去 后再加入优先队列,然后再给列的tag加上 (表示给所有列都减去了一个 ),这样就可以保证每次取的都是当前最大的行或者列。
事实上,这个思路是错误的,或者说不好处理这种情况:存在行最大值和列最大值相同的情况。比如样例:
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
在第一个样例中应该先取行,而第二个中应该先取列。
题解思路
回到正确的思路,我们还是有结论:取行和列互不影响。我们错误的贪心在于无法处理行和列相等时,应该先取行还是先取列。我们跳过这个问题,既然行和列互不影响,我们考虑答案的结构:答案一定是取 次行最大和 次列最大。那么很显然, 和 是我们可以枚举的,而取 次行最大和 次列最大,这是我们可以先行预处理出来的,再做前缀和即可。然后枚举 ,那么 ,每次的答案就是 。但是,我们还需要考虑行和列会有交叉操作:假设我们取了 次行,那么每一列的值都应该相应的减少 ,所以我们取 次列时,这一部分是多计算的(也就是把 多算了 次)。所以最后的答案应该减掉 ,那么最后的答案应该是:
$$ans = \max_{i=0}^k (pre_{row_i} + pre_{col_{k-i}} - i \times p \times (i - p)) $$tips: 要开到 。
参考代码
#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; }
- 1
信息
- ID
- 230
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 9
- 标签
- 递交数
- 14
- 已通过
- 2
- 上传者