关于贪心证明疑问
查看原帖
关于贪心证明疑问
251775
galiyuebing楼主2023/5/24 21:02

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

*/
2023/5/24 21:02
加载中...