头歌 2022 春第一期 Greeker‘s party 14 周

学校有 n 每家超市都有预约开始时间 t s t_s ts，预约结束时间 t e t_e te，单位时间预约成功率 p p p，和渴望值 w w w。请帮他计划什么时候抢哪家超市，获得最大的购物愉悦感。购物愉悦 = 成功概率 * 渴望值 * 时间 * 1000 1000 1000。为了防止浮点误差，题目中给出的成功率 p p p 已经乘以过 1000 1000 1000 了。 最大的购物乐趣总和模型 19260817 19260817 19260817。

做题前先看数据范围，发现超市数量最多 100 100 100，预约开始时间和预约结束时间小于预约结束时间 1 0 4 10^4 104，推断出时间复杂度满足 100 × 1 0 4 100 \times 10^4 100×104 即可，从而推断出解法是：遍历每个时间点 t i t_i ti​，比较所有在这个时间点开放的超市的权重（权重可以理解为预约成功率 * 渴望值 * 1000），挑选出一个最大的超市进就好了。

小的优化是，可以预先求出所有超市最早的预约开始时间和最晚的预约结束时间，就不用遍历 1 ∼ 1 0 4 1 \sim 10^4 1∼104 的所有时间点了。

for (int i = 0; i < n; i++) {
	// 0：预约开始时间 1：预约结束时间 2：预约成功率 3：渴望值
	cin >> nums[i][0] >> nums[i][1] >> nums[i][2] >> nums[i][3];
	start = min(start, nums[i][0]);
	end = max(end, nums[i][1]);
};

int ans = 0, mod = 19260817;
for (int i = start; i < end; i++) {
	int tmp = 0;
	for (vector<int>& num : nums)
		if (num[0] <= i && i < num[1]) // 这家超市在这个时间点开门
			tmp = max(tmp, num[2] * num[3]);
	ans = (ans + tmp) % mod;
};

时间复杂度是 O ( n T ) O(nT) O(nT)，其中 T T T 是预约时间结束和开始的最大差值。空间复杂度是 O ( n ) O(n) O(n)。完整代码见 GitHub。

这道题目的最优时间复杂度应该可以降至 O ( n 2 ) O(n^2) O(n2)，即与预约开始和结束时间完全无关。在这里我提供一个基于 贪心算法 的思路：首先直接对超市进行排序，权重大的超市排在前面，优先选择。用 并查集 维护已经被选择的 时间段，对于当前超市，我们在它的预约开始时间至预约结束时间这一时间段内，将已经被选择的 时间段 排除掉之后，其他时间段都选择当前超市即可，具体实现大家有兴趣可以尝试一下呀。

超市中商品共有 N 件，给出每件商品的商品编号 n，价格 m 和意愿值 v，请输出购物总金额不超过 500 元时能获得的最大意愿值。

这其实是道经典的背包问题，但作为高中没有打过 OI 的菜狗，我还是选择用通俗易懂的理解方式来完成这道题。

因为商品的个数是有限的，所以说我们的最外层循环肯定是遍历各个商品。对于每个商品，我们都可以选择买与不买，那么既然求的是 500 元以内，那么就是说 1 ~ 500 元的购买方案都是被接受的。

我们维护一个大小为 500 + 1 的数组 dp，dp[i] 就代表总共购买 i 元时能够获得的最大意愿值，比如说现在 dp[203] = 20 即 203 元能够获得最大 20 的意愿值，那么假如当前的商品价格是 100 意愿值是 10，则我们就要更新 dp[203 + 100] 为 min(dp[203 + 100], dp[203] + 10)。而对于每个商品，我们都要不厌其烦地从价格为 0 更新到 500 - price，注意实现时价格应按 从大到小 进行遍历，防止一个商品重复买多次。如果从小到大的话，在上面这个例子中就还会继续更新 dp[303 + 100] 为 min(dp[303 + 100], dp[303] + 10)，如果 dp[303] 已经是被 dp[203] + 10 更新过了的话，意味着你重复购买了这件商品两次，不符合题意，而从大到小就不会发生这种情况。

for (int i = 0; i < N; i++)
	// id, price, weight
	cin >> nums[i][0] >> nums[i][1] >> nums[i][2];

for (int i = 0; i < N; i++)
	for (int j = 500 - nums[i][1]; j >= 0; j--)
		dp[j + nums[i][1]] = max(dp[j + nums[i][1]], dp[j] + nums[i][2]);
	
cout << *max_element(dp.begin(), dp.end()) << endl;

时间复杂度是 O ( 500 N ) O(500N) O(500N)，空间复杂度是 O ( N ) O(N) O(N)，完整代码见 GitHub。

在第二题的基础上，商品变成了可以无限续杯了，但你的钱还是只有 500 元。

要是可以抢到东区教超，我一定拿这 500 元买 两箱瓜子，因为我对每包瓜子的期望值都是 + ∞ + \infty +∞。我又在做梦，打扰了，回归正题。

所以这道题就是在第二题的基础上加上了 商品可无限重复 的假设，正如我上题所述，只要价格是从小到大更新的，就可能会重复计入某个商品，这不正合我意？所以好得很，代码只要改一行就过了。

for (int i = 0; i < N; i++)
	// id, price, weight
	cin >> nums[i][0] >> nums[i][1] >> nums[i][2];

for (int i = 0; i < N; i++)
	for (int j = 0; j <= 500 - nums[i][1]; j++)
		dp[j + nums[i][1]] = max(dp[j + nums[i][1]], dp[j] + nums[i][2]);
	
cout << *max_element(dp.begin(), dp.end()) << endl;

当然，这样的时间空间复杂度和上题完全一样。时间复杂度是 O ( 500 N ) O(500N) O(500N)，空间复杂度是 O ( N ) O(N) O(N)，完整代码见 GitHub。

这周周赛题目整体比较流畅，难度循序渐进，第二第三题达到了力扣 Medium 的水平，对于经常混力扣的小朋友（指我）来说，也不算太难。这次也彻底放开了 STL 库的限制，非常感谢主办方能够考虑到同学们的一些小建议，也建议无论是大一小朋友还是大二在被数据结构折磨的苦命人，都有时间去看看 STL 的原理及其使用，比如我就因为不知道 vector 的 insert 操作是 O ( N ) O(N) O(N) 而被反复 鞭尸 了（开个玩笑），这更督促我好好看《STL 源码分析》，不能再摸鱼了。

最近把 minik8s 的网络部分总算是弄得差不多了，就差整合了，第一次面对要做这么大整合的项目还是有点措手不及。当然，最难办的还是俺的操作系统啊，两个月的网课录屏俺来了，还有十几天我真的会谢，还好是开卷，不说了，去整笔记了！

好啦，以上就是第十四周周赛的全部内容，欢迎关注我的 GitHub 账号。