题解 P2123 【皇后游戏】

### 做法 令$d_i = sgn(a_i - b_i)$ 先按$d_i(-1,0,1)$顺序把大臣分为三组，在每一组内分别排序： 1. $d_i=-1$，按$a_i$升序排序。 2. $d_i=0$，以任意顺序排序。 3. $d_i=1$，按$b_i$降序排序。 求出$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) \le \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$时符合$( * )$式即可。 1. $d_i = d_j \le 0$：$a_i \le a_j$，满足左边；$a_i \le b_i$，满足右边。 2. $d_i = d_j =1$：$b_j < a_j$，满足左边；$b_j < b_i$，满足右边。 3. $d_i < d_j$：$b_j \le a_j$，满足左边；$a_i \le b_i$，满足右边。 ### 代码 ```c++ #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); } } ```