leetcode 周赛 529
作者: | 更新日期:
误入歧途,贪心只贪了一半
本文首发于公众号:天空的代码世界,微信号:tiankonguse
零、背景
回头看,这次比赛不难。
但是我最后一题贪心只贪了一半,DP+贪心做的,超级复杂,昨晚已经比赛结束好久了。
本场题型概览如下。
A 题:枚举
B 题:树形DP
C 题:博弈DP
D 题:按最小值分组 + 二分
一、统计优势元素的数量
题意:给一个数组,问有哪些位置的元素大于相邻元素的平均值。
思路:枚举
按题意枚举判断即可。
注意事项:除法转乘法可以避免精度问题。
二、使数组中所有元素相等的最小成本
题意:给一个数组,可以执行人任意次操作。
每次操作选择一个位置,然后将这个位置的左边或者右边的元素都设置为当前元素,代价是当前元素与设置个数的乘积。
问使数组中所有元素相等的最小成本。
思路:贪心
显然,向左设置与向右设置最多操作一次。
想要使所有元素都相等,向左与向右设置的值必须相同。
中间没设置,说明中间的元素也与设置值都相同。

故可以得到贪心策略:枚举所有相等的连续区间,然后把左右设置,判断是否可以得到更小的代价。
复杂度:O(n)
注意事项:第一个和最后一个不能是枚举的区间。
三、信号激活的最早时刻
题意:给一个有向图,边的值代表从一个点到另一个点的时间。
起初节点 0 处于激活状态,其他节点至少被不同入度节点访问指定次数后,才能激活,访问出度节点。
问从节点 0 开始,每个节点的最早激活时间。
思路:带限制的单源最短路
还是按有限图进行 BFS。
只有一个节点入度超过指定次数后,再加入后续节点。
复杂度:O(E log(E))
requiredSignals[0] = 1;
min_queue<pair<ll, int>> que;
que.push({0, 0});
ans[0] = 0;
while (!que.empty()) {
auto [t, u] = que.top();
que.pop();
inDegree[u]++;
if (inDegree[u] != requiredSignals[u]) continue;
ans[u] = t;
for (auto [v, delay] : g[u]) {
que.push({t + delay, v});
}
}
四、删除数组的最小代价
题意:给一个数组,每次可以删除一个长度至少为2的连续区间,代价是区间左右端点之和。
问最少需要多少成本,可以把整个数组删除。
思路:贪心
错误思路1:划分没有交集的区间。

反例:-5 -5 10000 -5 -5
答案是 -20,不是 -10。

然后分析区间各种嵌套的情况,可以发现,内部的区间不会再次嵌套,即如下图。

不嵌套时,代价是 AB + CD。
嵌套时,代价是 AD + BC。
两个代价都等于 A+B+C+D。
故,任何嵌套的最优答案,都可以转化为不嵌套。
那选择哪些点才会更优呢?
显然,如果存在两个数之和大于0,则肯定不能选择这两个数字。
所以,需要选择所有负数,如果还剩一个,再与最小的非负数判断和是否小于0。
此时,就可以贪心得到下面的图形。
最外层一些相邻的大区间,每个大区间内有允许不连续的小区间。

通过插头DP与复杂的插头状态转换,即可 O(n) 时间内解决。
vector<Node> preCost(4); // 最小成本,最大负数, 最小非负数
// preCost[0] 负数个数为偶数个的最小成本
// preCost[1] 负数个数为奇数个数,剩余负数未使用的的最小成本
// preCost[2] 负数个数为奇数个数,剩余负数已使用的的最小成本
// preCost[3] 当前位置为右区间的最小成本
反思:最外层的大区间是否可以交换呢?
发现,只要满足最外层的大区间整理相邻连续,则是可以的。
如下图,左右两个大区间合并为一个,总代价依旧是所有区间端点之和,总代价不变。

因此,我们可以把所有大区间合并为一个,总代价依旧不变。
如下图,左右两个端点相连,则内部的所有小区间可以任意选择,依旧可以使用上诉的贪心。
只需要统计所有负数,最小非负数、最大的负数,即可判断内部小区间的最优答案。

五、最后
这次比赛其实不难,但是我最后一题贪心了一半,发现可以使用插头DP做,就敲代码了。
插头DP的状态很复杂,需要一个个分析状态转移方程,比较消耗时间。
赛后发现整体都可以贪心的,直接所有负数求和,再根据负数个数的奇偶性修正下就可以了。
《完》
-EOF-
本文公众号:天空的代码世界
个人微信号:tiankonguse
公众号 ID:tiankonguse-code
本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。
