贪心（二）
xukaiyi_kaiyi
·
·
个人记录
好了好了又来难受了，贪心真吐了（二）
这是三年前首A的绿题
P1080
我承认这题有个过分毒瘤的地方：高精度
但这并没有影响到这道题贪心的大难度
像上次一样，当我们试图写一个式子
*$&!@*@&($(@&&#&!#&^$&&*$&$&@#&$&
写不出来好吧……
慢慢来：
第x个人：(\prod_{i=1}^{x-1}a_i) \div b_x
第x+1个人：(\prod_{i=1}^{x}a_i) \div b_{x+1}
显然有很多相同的部分，先提取一下：
第x个人：(\prod_{i=1}^{x-1}a_i) \div b_x
第x+1个人：(\prod_{i=1}^{x-1}a_i) \times a_x \div b_{x+1}
重复部分\prod_{i=1}^{x-1}a_i记为S
第x个人：S \div b_x
第x+1个人：S \times a_x \div b_{x+1}
记a_x,a_{x+1},b_x,b_{x+1}分别为m,n,p,q:
即要求max(S \div p,S \times m \div q)的最小值。
当x与x+1颠倒：
max(S \div q,S \times n \div p)
若要求颠倒前是对的，则需max(S \div p,S \times m \div q)<max(S \div q,S \times n \div p)
显然S直接提出来消掉个啥呀S可以是零！
不过那样就没必要比大小了（认真）
拿出柿子
max(1 \div p,m \div q)<max(1 \div q,n \div p)
得知
n \div p > 1 \div p
m \div q > 1 \div q
(n,m都是正整数嘛)
这时候，如果要求后者大于前者，1 \div q就不能是后者最大值（前者至少是m \div q）
那么1 \div q<n \div p
前者如果1 \div p更大就没必要比较了，所以使用要求n \div p > m \div q
简单移项，n \times q > m \times p
即a_x \times b_{x+1} < a_{x+1} \times b_x
才推完……