J

共个武器, 每个武器都能升m级, 给出一个n*m的矩阵c, 第i行第j列代表i武器从j-1升到j级的花费(可能为负), 又给出一个长度为m的数组, 第i个数代表如果每个武器都升到i级(或以上), 就能获得这个奖励(可能为负), 问最多能得到多少钱.

可以发现, 如果升不到j-1级就到不了j级, 换句话说, 升到j级肯定取了前面所有的花费, 奖励的数组也是同理, 所以, 这个矩阵和数组都可以先求前缀和, 得到升到当前级的总花费(奖励).

枚举第等级为最低等级, 就是说每个武器等级都必须>=这个等级. 那么就暂时不需要考虑奖励的问题, 每个武器i就可以贪到中的最小值作为花费, 然后求和加上奖励就好了. 但是这样又会出现一个问题: 所有的武器都贪到超高的等级去了, 最低等级就发生了变化, 奖励就不是由我们枚举的唯一确定了. 解决这个问题也是很简单的, 只需要枚举每个武器, 选一个倒霉蛋调回最低等级, 然后加上花费的差值即可. 下(xjb)证这样做是合理的: 他们不选最低等级()作为目标等级, 肯定是因为到有一个花费更小的位置, 所以把他调回l肯定是要扩大花费的. 而我们只要有一个武器处于最低等级l即可唯一确定奖励是什么, 所以倒霉蛋是唯一的. 选倒霉蛋当然是选这个差值最小的了, 这样保证扩大的花费是最小的.

前缀和O(m*n)+O(m), 枚举最低等级O(m)*(每个武器O(n)*寻找l到m最小花费O(lg(m))+选倒霉蛋O(n))

总复杂度:

新知识: 如果怕骚的地方写错了, 而题意时间限制又不能写暴力, 可以在本地和暴力写对拍. 例如本题, 如果rmq怕写错,就可以把rmq先换成枚举取最小值, 然后在本地对拍就好了. D题也是这样, 二分和暴力对拍(虽然说证明了二分是错的...), 但是完全可以用它来证明答案在一定范围之内, 暴力枚举没必要枚举很大的范围之内.(D题)

ll c[1005][1005]; ll d[1005]; int _, m, n; int lg[1005]; struct RMQ { rmq模板 void RMQ_init1() {....} void RMQ_init2(int nn) {....} ll RMQ_min(int L, int R) {....} } rmq[1005]; ll getMin(int line, int l, int r) { /* //暴力,用于对拍 ll ans = INF; for (int i = l; i <= r; i++) { checkMin(ans, c[line][i]); } return ans;*/ return rmq[line].RMQ_min(l, r); } void init() { int caz=0; _ = read(); while (_--) { ll ans = 0; n = read(), m = read(); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { c[i][j] = c[i][j - 1] + read(); } } for (int k = 1; k <= m; ++k) { d[k] = d[k - 1] + read(); } rmq[1].RMQ_init1(); for (int i = 1; i <= n; ++i) { for (int j = 0; j <= m; ++j) { rmq[i].A[j] = c[i][j]; } rmq[i].RMQ_init2(m); } for (int l = 0; l <= m; ++l) { int flag = 0; ll tmp = 0; ll now[1005]; for (int i = 1; i <= n; ++i) { now[i] = getMin(i, l, m); if (now[i] == c[i][l])flag = 1; tmp += now[i]; } if (!flag) {//没有人作为最小值 ll minC = INF; for (int i = 1; i <= n; ++i) { checkMin(minC, c[i][l] - now[i]); } tmp += minC; } checkMax(ans, d[l] - tmp); } printf("Case #%d: ",++caz); write(ans); enter; } } int main() { init(); return 0; }

D

有n个物品, 每个物品有大小, 现在要搞k个桶, 小明会一个个填满这些桶, 每个桶放当前能放的最大的物品, 现在让你确定桶的最小合法size使得小明能把这些物品都放进桶里.

这个题没有单调性, 不能二分.

令, 我们可以知道, 答案一定,我们就确定了下界(最优的情况下, 每个数恰好是avg(a)). 此外, 最坏情况就是一半的数为, 另一半为, 这样, 我们如果开桶大小为就放不下了, 考虑到这种情况, 我们就会发现桶大小的上界为. 枚举找到合法的最小桶size即可.

新知识: (ljbnb)

①这一场告诉我们, 有些看上去是贪心/二分的题, 可能贪心策略不合法/没有单调性, 他们隐藏的很深, 要注意.

②此外, 一些题的确要分析它的答案最紧能确定在哪个范围内. 

这个范围是不是暴力就能解决了(是不是能把答案范围缩紧到能用暴力). 或者这个答案的范围能给我们另一些启发和灵感.

int _, n, k, a[1005], caz = 0; bool jug(int pos) { vector<int> v(a + 1, a + n + 1); int kk = k; int sz = pos; while (kk > 0) { int pp = lower_bound(v.begin(), v.end(), sz) - v.begin(); if (pp != v.size() && v[pp] == sz) { sz -= v[pp]; v.erase(v.begin() + pp); } else if (pp == 0) { sz = pos; kk--; continue; } else { sz -= v[pp - 1]; v.erase(v.begin() + pp - 1); } if (v.empty())return true; } return false; } void init() { _ = read(); while (_--) { n = read(); k = read(); int sum = 0; for (int i = 1; i <= n; ++i) { a[i] = read(); sum += a[i]; } sum /= k; sort(a + 1, a + n + 1); int l = max(a[n], sum), r = sum * 2; int ans = r; while (l <= r) { if (jug(l)) { checkMin(ans, l); break; } l++; } printf("Case #%d: %d\n", ++caz, ans); } } int main() { init(); return 0; }