目录
- 贪心
- 贪心应用
- P1561 [USACO12JAN] Mountain Climbing S
- P11323 【MX-S7-T1】「SMOI-R2」Happy Card
- 反悔贪心
- P1484 种树
- AGC018 C Coins
- P11268 【MX-S5-T2】买东西题
- Sol 1
- 贪心应用
贪心
自己中の光線銃 乱射する 強者のナンセンス
オートクチュールで作る 殺しのライセンス
分断を生んじゃった椅子取りゲーム 無痛分娩で授かるベイブ
壮大な内輪ノリを歴史と呼ぶ
选取局部最优解达到全局最优解的算法。
贪心的正确性需要证明，有如下证明方法：
- 微扰
- 范围缩放
- 决策包容
- 反证
- 数学归纳
贪心应用
P1561 [USACO12JAN] Mountain Climbing S
是一道普通贪心题。
贪心策略是使有牛下山时尽可能使山上有牛。
需要将牛分为 \(U(i) \ge D(i)\) 和 \(U(i) \lt D(i)\) 两种情况，让第二类牛先上能满足贪心。
其他比较简单。时间复杂度 \(\mathcal{O}(n)\)。
code
const int N = 2.5e4 + 5;struct node { int up, dw; } a[N];
int n, ut[N], dt[N];bool cmp(node a, node b) {if (a.up < a.dw) {if (b.up < b.dw) return a.up < b.up;else return 1;} else {if (b.up < b.dw) return 0;else return a.dw > b.dw;}
}int main() {read(n);rep(i, 1, n) read(a[i].up, a[i].dw);sort(a + 1, a + n + 1, cmp);rep(i, 1, n) ut[i] = ut[i - 1] + a[i].up;rep(i, 1, n) dt[i] = max(dt[i - 1], ut[i]) + a[i].dw;write(dt[n]);return 0;
}
P11323 【MX-S7-T1】「SMOI-R2」Happy Card
\(\color{#39C5BB}{[EASY]}\)
需要观察到“炸”是三带一，即三张相同的牌可以带任意一张牌。
贪心地尽可能出三带一是对的，这点在模拟出牌后即可发现。
然后将牌分成 \(3\) 个一组，\(2\) 个一组，单独一组，分别讨论答案就好了。
code
const int N = 3e5 + 5;int T, n, v[N];
i64 cnt[4], ans;void init() {cnt[1] = cnt[2] = cnt[3] = 0; ans = 0;
}void solve() {read(n); init();rep(i, 1, n) read(v[i]);rep(i, 1, n) {cnt[3] += v[i] / 3;if (v[i] % 3) cnt[v[i] % 3]++;}if (cnt[3] <= cnt[1]) return write(cnt[3] + (cnt[1] - cnt[3]) + cnt[2], '\n'), void();if (cnt[3] - cnt[1] <= 2 * cnt[2]) return write(cnt[3] + (2 * cnt[2] - (cnt[3] - cnt[1]) + 1) / 2, '\n'), void();ans += cnt[2] * 2 + cnt[1];cnt[3] -= (2 * cnt[2] + cnt[1]);ans += (cnt[3] / 4) * 3; cnt[3] %= 4;if (cnt[3] == 3) ans += 3;else if (cnt[3] == 2 || cnt[3] == 1) ans += 2;write(ans, '\n');
}int main() {read(T);while (T--) solve();return 0;
}
反悔贪心
不需要选最优解，从一个较劣的情况变为最优解。
P1484 种树
反悔贪心板子。
先贪心选最大，然后做一个用于反悔的坑。
变成链表上操作，方便模拟题意。
时间复杂度 \(\mathcal{O}(n\log n)\)。
code
const int N = 6e5 + 5;int n, k, a[N];
int pre[N], Next[N];
priority_queue<pii> que;
bool vis[N];
i64 ans;int main() {read(n, k);rep(i, 1, n) read(a[i]);rep(i, 2, n) pre[i] = i - 1;rep(i, 1, n - 1) Next[i] = i + 1;rep(i, 1, n) que.push({a[i], i});while (k) {while (vis[que.top().second]) que.pop();int val = que.top().first, pos = que.top().second;if (val < 0) break;int pval = a[pre[pos]], nval = a[Next[pos]];a[++n] = pval + nval - val; que.push({a[n], n});ans += val, vis[pos] = 1, vis[pre[pos]] = 1, vis[Next[pos]] = 1;Next[pre[pre[pos]]] = n, pre[n] = pre[pre[pos]];Next[n] = Next[Next[pos]], pre[Next[Next[pos]]] = n; k--;}write(ans);return 0;
}
AGC018 C Coins
开始随便选，然后交换即可。
用六个堆维护每个人换成另外两种币的收益。
显然会有两两互换或三人互换的情况。容易证明多人互换的情况可以用前两种情况表示。
容易证明时间复杂度是 \(\mathcal{O}(n\log n)\)。code。
P11268 【MX-S5-T2】买东西题
\(\color{#FFA500}{[NORMAL-]}\)
Sol 1
50 pts 简单，考虑每个优惠券会对那些商品起作用。
发现作用区间为一段后缀，作用形如替换降价价格，考虑用线段树计算答案。
首先将优惠券按限制从大到小排序。然后对于每个优惠券，令它对它起作用区间内降价最少的替换，这样一定不劣。
因为后缀只会变长，这样处理出了局部最优解。
我的错误
考场上觉得需要按降价对优惠券进行排序。
一个很典的问题，局部最优解不是全局最优解。
因为把后面的位置占了，有后效性，而上面的没有。
code
const int N = 1e6 + 5;struct Node { int a, b; } a[N], b[N];
int n, m, c[N], d[N], tr[N << 2];
i64 ans;void up(int rt) { tr[rt] = d[tr[ls]] > d[tr[rs]] ? tr[rs] : tr[ls]; }void build(int rt, int l, int r) {if (l == r) return tr[rt] = l, void();int mid = (l + r) >> 1;build(ls, l, mid), build(rs, mid + 1, r);up(rt);
}void update(int rt, int l, int r, int p, int v) {if (l == r) return d[p] = v, void();int mid = (l + r) >> 1;if (p <= mid) update(ls, l, mid, p, v);else update(rs, mid + 1, r, p, v);up(rt);
}int query(int rt, int l, int r, int L, int R) {if (L <= l && r <= R) return tr[rt];int mid = (l + r) >> 1, pos, val = 1e9 + 5;if (L <= mid) {int p = query(ls, l, mid, L, R);if (d[p] < val) pos = p, val = d[p];}if (mid < R) {int p = query(rs, mid + 1, r, L, R);if (d[p] < val) pos = p;}return pos;
}int main() {read(n, m);rep(i, 1, n) read(a[i].a, a[i].b);rep(i, 1, m) read(b[i].a, b[i].b);sort(a + 1, a + n + 1, [&](Node a, Node b) { return a.a < b.a; });sort(b + 1, b + m + 1, [&](Node a, Node b) { return a.a > b.a; });rep(i, 1, n) c[i] = a[i].a, d[i] = a[i].a - a[i].b;build(1, 1, n);rep(i, 1, m) {int l = lower_bound(c + 1, c + n + 1, b[i].a) - c;if (l > n) continue;int p = query(1, 1, n, l, n);if (d[p] < b[i].b) update(1, 1, n, p, b[i].b);}rep(i, 1, n) ans += a[i].a - d[i];write(ans);return 0;
}