皇后游戏_(贪心）

原题链接：P2123 皇后游戏 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：国王游戏_(贪心)的升级版，大臣排队，每人左右手各写一个数字，每个人领到的奖金是max(前一个大臣的奖金，前i个大臣的左手数字和)+自己的右手数字，第一个大臣是自己的左右手相加，求一个排序使得奖金最大的最小

思路

首先思路与国王游戏类似，先使用相邻交换法

首先，某个位置上大臣是i，其后为j

已知每个大臣都至少是前一个大臣的奖金加自己右手的值，即后者为奖金大者

最大为

$$\begin{array}{rl}A& =max(su{m}_j,an{s}_i)+b_j=max(su{m}_i+a_j,max(su{m}_i,an{s}_{i-1})+b_i)+b_j\\ & =max(su{m}_i+a_j+b_j,su{m}_i+b_i+b_j,an{s}_{i-1}+b_i+b_j)\end{array}$$

交换之后

$$\begin{array}{rl}B& =max(su{m}_i,an{s}_j)+b_i=max(su{m}_j+a_i,max(su{m}_j,an{s}_{j-1})+b_j)+b_i\\ & =max(su{m}_j+a_i+b_i,su{m}_j+b_j+b_i,an{s}_{j-1}+b_j+b_i)\end{array}$$

要满足i在前为最优，则应该

$A<=B$

发现都有$ans+b_j+b_i$ ，又此时要A⇐B，ans项相等，则满足另外两项A⇐B，如果满足，则ans项存不存在对推导无影响，如果不满足，则A⇐B不满足，需要交换A，B，所以ans可以去掉

等式变成

$$\begin{array}{rl}max(su{m}_i+a_j+b_j,su{m}_i+b_i+b_j)& <=max(su{m}_j+a_i+b_i,su{m}_j+b_j+b_i)\\ max(sum+a_i+a_j+b_j,sum+a_i+b_i+b_j)& <=max(sum+a_j+a_i+b_i,sum+a_j+b_j+b_i)\end{array}$$

去掉sum

$$max(a_i+a_j+b_j,a_i+b_i+b_j)<=max(a_j+a_i+b_i,a_j+b_j+b_i)$$

化简

$$max(a_j,b_i)+a_i+b_j<=max(a_i,b_j)+a_j+b_i$$ $$max(a_j,b_i)-a_j-b_i<=max(a_i,b_j)-a_i-b_j$$

发现max取出的项被减掉，也就是变成了

$$min(a_j,b_i)<=min(a_i,b_j)$$

或许可以直接按这个顺序排序，但是其实这种排序不具备传递性，也就是虽然两两满足这个条件，但是满足这个顺序的结果在两两之间最小，但是在跨越多个后不一定最小

1 1
1 6
7 3

and

7 3
1 1
1 6

结果不同，但是都满足判断

正解

$min(a_i,a_j)<=min(a_j,b_i)$

式子有必要性，可以试着推导更细的排序，可以发现上面例子正是有不同的三类

可以通过这个式子推出正确的排序

1. 当$a_i<b_i，a_j<b_j按a_i<=a_j$
2. 当$a_i=b_i，a_j=b_j$ 随意排
3. 当$a_i>b_i,a_j>b_j按b_i>=b_j$

另外组间的排序满足1组在2组前可以满足，2组在3组前可以满足，即可以按 1，2，3排序

代码

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long LL;
 
const int N = 2e4 + 10;
 
struct DC{
    LL a, b;
    LL sum;
    int d;
}dc[N];
 
bool cmp(DC x, DC y)
{
    if(x.d != y.d)
        return x.d < y.d;
    else if(x.d < 0)
        return x.a < y.a;
    else
        return x.b > y.b;
}
 
int t;
int n;
 
 
void solve()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> dc[i].a >> dc[i].b;
        dc[i].d = dc[i].a <= dc[i].b ? -1 : 1;
    }
 
    sort(dc, dc + n, cmp);
 
    LL sum = dc[0].a; 
    dc[0].sum = dc[0].a + dc[0].b;
    for(int i = 1; i < n; i ++)
    {
        sum += dc[i].a;
        dc[i].sum = max(sum, dc[i - 1].sum) + dc[i].b;
    }
 
    cout << dc[n - 1].sum << endl;
}
 
 
int main()
{
    cin >> t;
    while(t --)
    {
        solve();
    }
 
    return 0;
}