rt,本蒟蒻妄图用不完全归纳法去解贪心策略
但到一半发现解不出来了,希望有大佬指点一下,万分感谢
/*
假设只有两个人(不去想国王,没意义 )
设变量l1,r1为排在前面的人的左右手数值,l2,r2为排在后面的人的左右手数值
因此l1/r2 < l2/r1 <=> l1*r1<l2*r2
增加变量,假设有三个人
设l1,r1,l2,r2,l3,r3,意义同上(1在2,3前面,2在3前面)
则 l1/r2 + (l1*l2)/r3 < l1/r3 + (l1*l3)/r2 (123<132) 一
且 l1/r2 + (l1*l2)/r3 < l2/r1 + (l1*l2)/r3 (123<213) 二
和 l1/r2 + (l1*l2)/r3 < l3/r2 + (l2*l3)/r1 (123<231) 三
及 l1/r2 + (l1*l2)/r3 < l3/r1 + (l1*l3)/r2 (123<312) 四
与 l1/r2 + (l1*l2)/r3 < l3/r2 + (l2*l3)/r1 (123<321) 五
---------------------------------------------------------------------------------------------------
整理一式得 l1*r3 + l1*l2*r2 < l1*r2 + l1*l3*r3 <=> l2*r2 - r2 < l3*r3 - r3
整理二式得 l1/r2 < l2/r1 <=> l1*r1 < l2*r2
整理三式得 l1*r1*r3 + l1*r1*l2*r2 < l3*r3*r1 + l2*r2*l3*r3 <=> l1*r1(l2*r2 + r3) < l3*r3(l2*r2 + r1)
整理五式得 l1*r1*r3 + l1*r1*l2*r2 < l3*r3*r1 + l2*r2*l3*r3 <=> l1*r1(l2*r2 + r3) < l3*r3(l2*r2 + r1)
整理四式得 l1*r1*r3 + l1*r1*l2*r2 < l3*r3*r2 + l1*r1*l3*r3 <=> l1*r1(l2*r2 + r3) < l3*r3(l1*r1 + r2)
---------------------------------------------------------------------------------------------------
重新整理逻辑:首先123顺序为既定事实,而要找的是排列顺序的比较依据
由四式减五式得 l1*r1 + r2 - l2*r2 -r1 > 0 <=> l1*r1 -r1 > l2*r2 - r2 六
由六式与二式得 r1 < r2
*/