n个物品,a选了收益是ai,b选了收益是bi,双方轮流选,目的都是最大化自己的收益-对方的收益,都使用最优策略,n<=1e5。
sol:可以看成两只舔狗抢东西吃,东西就那么多,抢到就是赚,抢了别人的也是赚。 抢到一个物品对自己的收益是x,对对方造成的损失是y,显然每次都照着多的抢吧。 因此按照ai+bi排序轮流选择即可。 代码很简单,略。本文共 224 字,大约阅读时间需要 1 分钟。
n个物品,a选了收益是ai,b选了收益是bi,双方轮流选,目的都是最大化自己的收益-对方的收益,都使用最优策略,n<=1e5。
sol:可以看成两只舔狗抢东西吃,东西就那么多,抢到就是赚,抢了别人的也是赚。 抢到一个物品对自己的收益是x,对对方造成的损失是y,显然每次都照着多的抢吧。 因此按照ai+bi排序轮流选择即可。 代码很简单,略。转载于:https://www.cnblogs.com/Creed-qwq/p/10328056.html