贪心就是那么的恶心。
题目传送门
难度：
这种蓝题的贪心还是值得好好想一想的。
经过我们的多重猜测，我们应当按左右手之积升序排序，证明如下。
证
对于大臣 \(i\) 和 \(i+1\)，设 \(1\) 到 \(i+1\) 的最大值为 \(\alpha\)，\(1\) 到 \(i-1\) 的最大值为 \(\beta\)，则
\[\alpha=\max(\beta,\frac{\prod_{j=0}^{i-1} a_j}{b_i},\frac{\prod_{j=0}^{i} a_j}{b_{i+1}})
\]
令
\[v=\frac{\prod_{j=0}^{i-1} a_j}{b_i},s=\frac{\prod_{j=0}^{i} a_j}{b_{i+1}}
\]
设当 \(i\) 和 \(i+1\) 交换后比不交换后更优的最大值为
\[\gamma=\max(\beta,\frac{\prod_{j=0}^{i-1} a_j}{b_{i+1}},\frac{\prod_{j=0}^{i+1} a_j}{b_i})
\]
且 \(\gamma<\alpha\)，令
\[t=\frac{\prod_{j=0}^{i-1} a_j}{b_{i+1}},u=\frac{\prod_{j=0}^{i+1} a_j}{b_i}
\]
由于每个人手上的数字均为正整数，则
\[\prod_{j=0}^{i-1} a_j<\prod_{j=0}^{i} a_j<\prod_{j=0}^{i+1} a_j
\]
于是
\[\frac{\prod_{j=0}^{i-1} a_j}{b_{i+1}}<\frac{\prod_{j=0}^{i} a_j}{b_{i+1}},\frac{\prod_{j=0}^{i-1} a_j}{b_j}<\frac{\prod_{j=0}^{i+1} a_j}{b_i}
\]
即
\[s>t,u>v
\]
故 \(\alpha\) 只能等于 \(s\)，\(\gamma\) 只能等于 \(u\)，故
\[\alpha<\gamma \Leftrightarrow s<u \Leftrightarrow \frac{\prod_{j=0}^{i} a_j}{b_{i+1}} < \frac{\prod_{j=0}^{i+1} a_j}{b_i}
\]
同时除 \(\prod_{j=0}^{i} a_j\) 得
\[\frac 1{b_{i+1}}<\frac{a_{i+1}}{a_i \times b_i}
\]
即
\[a_i \times b_i<a_{i+1} \times b_{i+1}
\]
又由于 \(i+1\) 后面的与 \(i\) 和 \(i+1\) 的排列方式无关，故证毕。
代码就不放了。