国王游戏
题目链接:国王游戏
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\)