题解 P2123 【皇后游戏】

· · 题解

做法

令d_i = sgn(a_i - b_i)

先按d_i(-1,0,1)顺序把大臣分为三组，在每一组内分别排序：

求出c_n并输出。

证明

偏序关系

令P_{i,j}=\left \{ \begin{aligned} [d_i<d_j] & ,d_i != d_j \\ [a_i \le a_j] & ,d_i=d_j \le 0 \\ [b_i > b_j] & ,d_i=d_j=1 \end{aligned} \right.

（即按上述做法重载\le）

因为P_{i,j}不过是多个排序的复合，所以它满足自反、反对称和传递性，是一个偏序关系，可以以P_{i,j}作为\le来排序。

接下来只需要证明若P_{i,i+1}=1，则交换i和i+1不会使答案更优即可。

何时更优

注意到\forall 0 \le i < n,c_i \le c_{i+1}，所以交换时我们只需要考虑后一项的大小关系，什么时候交换不会导致答案变优呢？（下面以j=i+1；c是c_{i-1}；s=\sum_{k=1}^{i-1}a_k）

\max ( \max (c,s + a_i) + b_i,s + a_i + a_j) + b_j = \max \{ c , s + a_i , s + a_i - b_i + a_j \} + b_i + b_j \le \max \{ c, s + a_j , s + a_j - b_j + a_i \} + b_i + b_j

化简：\max (a_i, a_i - b_i + a_j ) \le \max (a_j,a_j - b_j + a_i)

两边同时减去a_i + a_j：\max (-a_j,-b_i) \le \max (-a_i,-b_j)

乘以-1：\min (a_j,b_i) \ge \min (a_i,b_j)

拆解成逻辑表达式：

(a_i \le a_j \lor b_j \le a_j) \land (a_i \le b_i \lor b_j \le b_i)(*)

在此相遇

至此，我们只需要验证P_{i,j}=1时符合( * )式即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50000;
struct Secretary
{
    int a, b, d;
} sty[N + 5];
inline bool cmp(const Secretary &x, const Secretary &y)
{
    if (x.d != y.d)
        return x.d < y.d;
    if (x.d <= 0)
        return x.a < y.a;
    else
        return x.b > y.b;
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n; ++i)
        {
            scanf("%d%d", &sty[i].a, &sty[i].b);
            sty[i].d = sty[i].a - sty[i].b;
            if (sty[i].d)
                sty[i].d /= abs(sty[i].d);
        }
        sort(sty + 1, sty + n + 1, cmp);
        ll c = 0, s = 0;
        for (int i = 1; i <= n; ++i)
        {
            s += sty[i].a;
            c = max(c, s) + sty[i].b;
        }
        printf("%lld\n", c);
    }
}