国王游戏
题目链接:国王游戏
ps:题目数据说明了要写高精度.
这个题的答案是(a.l * a.r < b.l * b.r)按照这个进行排序
题解中大部分只是如何证明排序是:
(a.l * a.r < b.l * b.r)
我来利用上面的贪心性质来推一下.
设国王左手的数为L,右手的数没什么用.....
还是对于两个人来说.
答案为:
第一个人排在第一位,第二个人排在第二位.
第二个人排在第一位,第二个人排在第一位.
两种情况下的结果大的那个是不会被选择的排在第一位的.
也就是
如果$$max(L * r_1,L * l_1 / r_2) < max(L / r_2,L * l_2 / r_1)$$的话,那么直接让我们假设的第一个人在前面
反之,直接让我们假设的第二个人在前面
这样排序是正确的.(可以交上去试一下,qwq)
之后
我们可以化简这个式子.
拆开后.考虑每一项作为答案.
第一项
(L * r_1)
(L * l_1 / r_2)
第二项
(L / r_2)
(L * l_2 / r_1)
大家会发现,(L * r_1)完全不可能作为答案,因为第二项(L * l_2 / r_1)中的他一定会比这个大.同理,(L * r_2)也不会被选择.
那么只剩下(L * l_1 / r_2)与(L*l_2/r_1)相比
两边同时乘以(r_2*r_1)除以(L)
成了这种形式
(l_1*r_1)
(l_2*r_2)
如果(l_1*r_1)大的话就是二(编号大的)在前面
如果(l_2*r_2)大的话就是一(编号小的)在前面
所以排序顺序是(l_1*r_1 < l_2*r_2)