【ZROI–21暑期AB组-Day3】OSU

题意#

见：21暑期AB组高端峰会 - Day3 - OSU - Zhengrui Online Judge ↗

或：T207786 [ZROI#1922] OSU - 洛谷 - 计算机科学教育新生态 ↗

分析#

柯西不等式：

$$\sum_{i=1}^{n}{{a_i}^2}\sum_{i=1}^{n}{{b_i}^2}\geq (\sum_{i=1}^{n}{a_ib_i})^2$$

题目想要：

$$\sum_{i=1}^{t}{p_ic^{i-1}}= w_0$$

利用柯西不等式：

$$\sum_{i=1}^{t}{{p_i}^2}\sum_{i=1}^{t}{c^{2(i-1)}}\geq (\sum_{i=1}^{t}{p_ic^{i-1}})^2= {w_0}^2$$

移项得到：

$$\sum_{i=1}^{t}{{p_i}^2}\geq \frac{{w_0}^2}{\sum_{i=1}^{t}{c^{2(i-1)}}}$$

不等式左侧即为答案，取最小值：

$$\operatorname{Ans}=\frac{{w_0}^2}{\sum_{i=1}^{t}{c^{2(i-1)}}}$$

可以 $\mathcal{O}(t)$ 计算。