CF725F Family Photos 做题记录

有 $n$ 个大小为 $2$ 的照片堆，每张照片可以用一个二元组 $(a,b)$ 描述，每个堆可以用一个四元组 $(a1,b1,a2,b2)$ 描述，表示堆顶的照片为 $(a1,b1)$，堆底的照片为 $(a2,b2)$。

Alice 和 Bob 要轮流取照片，Alice 先手，轮到某个人取时他可以选择跳过，若一轮中两人均选择跳过则游戏结束。

对于一张照片 $(a,b)$，Alice 取它能获得 $a$ 分，Bob 能获得 $b$ 分，位于堆底的照片要等到相应堆顶的照片被取掉才能取。

记 Alice 的得分和为 $ta$，Bob 的为 $tb$。Alice 的目标是最大化 $ta-tb$，Bob 则要最大化 $tb-ta$。

两人绝顶聪明，求出游戏结束时的 $ta-tb$。

$1\le n\le 10^5$，$0\le a1,b1,a2,b2\le 10^9$。

考虑每堆只有一张照片的情况，由于 $0\le a,b$ 所以每张照片必然都会被取走，那么考虑先令 $ta=\sum a,tb=\sum b$，则 Alice 取走 $(x,y)$ 会令 $ta-tb$ 加上 $x+y$，Bob 取走它也会令 $tb-ta$ 加上 $x+y$，所以两人必然会按照 $a+b$ 从大到小的顺序取走照片。

考虑推广到原题，但是有个问题就是不一定每张照片都被取走。考虑这样做的深层原因，对于两张照片 $(x1,y1)$ 和 $(x2,y2)$，若 $x1+y1>x2+y2$，则变形可得 $x1-y2>x2-y1$ 和 $y1-x2>y2-x1$，也就是说无论先后手先取 $(x1,y1)$ 肯定优。

那么不难发现对于一个照片堆 $(a1,b1,a2,b2)$：

• 若 $a1+b1\ge a2+b2$，则两人都想取走上面那个，那么对于这些堆中的照片按照 $x+y$ 从大到小排序，轮流取即可。注意这样堆顶的照片一定会先被取走；
• 否则 $a1+b1<a2+b2$，则变形得 $(a1-b2)+(b1-a2)<0$：
  • 若 $a1-b2<0$ 且 $b1-a2<0$，则双方均不想动这堆，这堆对答案没贡献；
  • 若 $a1-b2<0$ 且 $b1-a2>0$，则 Bob 会取这堆，对答案贡献 $a2-b1$；
  • 若 $a1-b2>0$ 且 $b1-a2<0$，则 Alice 会取这堆，对答案贡献 $a1-b2$；

时间复杂度 $O(n\log n)$。