CMO 2023 Day1T1

发布时间 2023-11-28 23:31:30作者: do_while_true

\(n=2^{2024}\) 时最优方案为 \(2,2,\cdots ,4\) 此时 \(\lambda_0=\frac{1}{1012}\)\(\lambda_{\min}\geq \lambda_0\)。对于 \(\lambda =\frac{1}{1012}\) 构造,令 \(n=\prod p_i\)\(p_i=n^{a_i}\) 其中 \(p\) 均为素数。那么问题转化为:

\(\sum a_i=1\),其中 \(a>\frac{1}{1012}\) 的要单独分组 \(a\leq \frac{1}{1012}\) 可以若干个分一组,但是要满足一组内的 \(\sum a\leq \frac{1}{1012}\)

充分性给出贪心构造策略:若存在 \(a_x+a_y\leq \frac{1}{1012}\) 那么将 \(x\) 组和 \(y\) 组合并成一个新的组,其大小为 \(a'=a_x+a_y\),若有多个合法的任选两个进行合并,直到不能合并为止,此时一定有组数 \(m\leq 2023\),即得到一个合法方案。

证明:若 \(m\geq 2024\),此时考虑 \(a_1\leq a_2\leq a_3\leq\cdots\leq a_m\),其中 \(a_1+a_2>\frac{1}{1012}\),那么一定有 \(a_2>\frac{1}{2024}\),则 \(a_3,a_4,\cdots,a_m\)\(>\frac{1}{2024}\) ,那么

\[\sum a=(a_1+a_2)+(a_3+a_4+\cdots+a_m)>\frac{1}{1012}+\frac{m-2}{2024}\geq \frac{1}{1012}+\frac{2022}{2024}=1 \]

\(\sum a=1\) 的条件不符,故 \(m\leq 2023\)