2025 华子笔试（4.16）

没做，从网上看了下题面，感觉很有意思

以及t1是假题吧，最优区间覆盖不是np hard吗？

这里贴一下T3的题解：

【前置知识：经典区间调度问题】

首先第一眼过去似乎是个比较典的区间调度，按照右端点排序后贪心，但显然这个做法可以被轻易hack掉——它无法满足占有ip最少。

n=1000，那么考虑n2做法：
vector  res;
对所有区间按照右端点升序排序；
work[i].id表示业务id，work[i].num第i个业务要占有多少ip；
第一层循环i：1-n
第二层循环表示自此开始进行普通区间调度贪心选取（按右端点）。

举个例子：
i=1的时候，能完成10个业务，占用20个ip；
i=2的时候，能完成10个业务，占用18个ip；
i=3的时候只能完成9个业务，那么再往后能完成的业务数量肯定会越来越少。
我们此时应该选取i=2对应的区间，将其加入到答案中，res.push_back(work[2].id)；

选取完2之后，
i=3和2冲突，跳过；
i=4的时候，能完成8个业务，占用14个ip；
i=5的时候，能完成8个业务，占用17个ip；
i=6的时候，能完成7个业务；
那么把i=4加入到答案中。
…
以此类推。

注意，若业务完成数量和占用ip数量都相等，需要比较一下左端点。

所以实际上只需要在经典区间调度外面加一层枚举起点即可。

end

若有错误欢迎指正

题面已经附图
#华为机试# #实习# #华为#