题号：nc16561 国王的游戏

题号：nc16561 国王的游戏

用ai表示左手，bi表示右手，ci表示钱数，i=0时为国王。 用数学归纳法证明：

当n=1时，答案唯一；当n=2时，即 a0b0a1b1a2b2

按12排序，c11=a0/b1，c12=a0×a1/b2； 按21排序，c22=a0/b2，c21=a0×a2/b1。 明显c21>c11，c12>c22，所以令ans1=c12，ans2=c21，比较这两项即可。 若12排法最大值小，则c12<c21，解得a1×b1<a2×b2。这里可知，相邻两者，ai×bi大者后置为优。

当n=k时，设前k项排序完成，并将最后一项命名为ak和bk。 则n=k+1时，将前k-1项乘积视为n=2时的a0，则只需排新项a(k+1)×b(k+1)和原最大项ak×bk相比即可，同样的排序之后，大项后置，钱数亦可知。

所以，以ai×bi排序即可，然后算最大者的钱。