2020-2021:teams:legal_string:jxm2001:other:错题集_5

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:other:错题集_5 [2021/03/10 18:14]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:other:错题集_5 [2021/08/24 11:25] (当前版本)
jxm2001
@@ 行 257: / 行 257: @@
 </code>
 </hidden>
+===== 3、CDN流量调度问题 =====
+[[https://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1003&cid=1029|2021CCPC华为云挑战赛 1003]]
+==== 题意 ====
+给定 $n$ 个网络和 $m$ 个额外结点。第 $i$ 个网络初始有一个结点，且最多被分配 $b_i$ 个结点，当被分配 $k$ 个结点时，费用为 $\lceil\frac {a_i}k\rceil$。
+最小化所有网络的费用和。
+==== 题解 ====
+易知使得每个网络的费用发生变化的 $k$ 只有 $O(\sqrt {a_i})$ 个，可以 $O\left(\sum_{i=1}^n a_i\right)$ 暴力预处理。
+然后设 $\text{dp}(i,j)$ 表示只考虑前 $i$ 个网络花费 $j$ 个额外结点的最小费用，然后状态转移只枚举有效的 $k$。
+总时间复杂度 $O(nm\sqrt a)$，个人感觉时间复杂度过大，但题目测试数据貌似比较水，所以可以过。
+ps. 本人一开始考虑优先队列，贪心取变化量最大的网络加结点，但实际受取整函数影响，变化量不是单调的，因此假了。

2020-2021/teams/legal_string/jxm2001/other/错题集_5.1615371295.txt.gz · 最后更改: 2021/03/10 18:14 由 jxm2001