[洛谷P2123]皇后游戏

难度：省选/NOI-

题目背景

        还记得 NOIP 2012 提高组 Day1 的国王游戏吗？时光飞逝，光阴荏苒，两年过去了。国王游戏早已过时，如今已被皇后游戏取代，请你来解决类似于国王游戏的另一个问题。

题目描述

        皇后有 n 位大臣，每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临，皇后决定为 n 位大臣颁发奖金，其中第 i 位大臣所获得的奖金数目为第i－1 位大臣所获得奖金数目与前 i 位大臣左手上的数的和的较大值再加上第 i 位大臣右手上的数。
        形式化地讲:我们设第 i 位大臣左手上的正整数为 a_i，右手上的正整数为 b_i，
        则第 i 位大臣获得的奖金数目为 c_i可以表达为:

$$c_i=\begin{cases} a_1+b_1 & i=1\\ \max\{c_{i-1},\displaystyle\sum_{j=1}^ia_j\} & 2\leq i\leq n \end{cases}$$

        当然，吝啬的皇后并不希望太多的奖金被发给大臣，所以她想请你来重新安排一下队伍的顺序，使得获得奖金最多的大臣，所获奖金数目尽可能的少。注意:重新安排队伍并不意味着一定要打乱顺序，我们允许不改变任何一位大臣的位置。

输入输出格式

输入格式:

        第一行包含一个正整数 T，表示测试数据的组数。
        接下来 T 个部分，每个部分的第一行包含一个正整数 n，表示大臣的数目。
        每个部分接下来 n 行中，每行两个正整数，分别为 a_i和 b_i，含义如上文所述。

输出格式:

        共 T 行，每行包含一个整数，表示获得奖金最多的大臣所获得的奖金数目。

输入输出样例

Sample input#1

1
3
4 1
2 2
1 2

Sample output#1

8

Sample input#2

2
5
85 100
95 99
76 87
60 97
79 85
12
9 68
18 45
52 61
39 83
63 67
45 99
52 54
82 100
23 54
99 94
63 100
52 68

Sample output#2

528
902

说明

        按照 1，2，3 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 10;
        按照 1，3，2 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 9;
        按照 2，1，3 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 9;
        按照 2，3，1 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 8;
        按照 3，1，2 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 9;
        按照 3，2，1 这样排列队伍，获得最多奖金的大臣获得奖金的数目为 8。
        当按照 3，2，1 这样排列队伍时，三位大臣左右手的数分别为:(1， 2)，(2， 2)，(4， 1)
        第 1 位大臣获得的奖金为 1 + 2 = 3;
        第 2 位大臣获得的奖金为 max{3， 3} + 2 = 5;
        第 3 为大臣获得的奖金为 max{5， 7} + 1 = 8。
        对于全部测试数据满足:T≤10，1≤n≤20000，1≤a_i，b_i≤10⁹。

题解

        考察数学推导，排序和贪心，难度很高。
        对于两个相邻的大臣i，j，假定i前方的a之和为p，i前的大臣c值为q，那么可以求出j的c值:

$$c_j=\max\{c_i，p+a_i+a_j\}+b_j$$

        这里c_i也可以求出:

$$c_i= \max\{q，p+a_i\}+b_i$$

        所以有

$$c_j=\max\{\max\{q，p+a_i\}+b_i，p+a_i+a_j\}+b_j$$

        即

$$c_j=\max\{q+b_i+b_j，p+a_i+b_i+b_j，p+a_i+a_j+b_j\}$$

        同理交换后有

$$c_j=\max\{q+b_j+b_i，p+a_j+b_j+b_i，p+a_j+a_i+b_i\}$$

        假定不交换更优，那么有

$$\max\{q+b_i+b_j，p+a_i+b_i+b_j，p+a_i+a_j+b_j\}\leq \max\{q+b_j+b_i，p+a_j+b_j+b_i，p+a_j+a_i+b_i\}$$

        把这个式子记作①。
        发现其中都有q+b_i+b_j这一项，把它们归结为max{a，b}≤max{a，c}。容易发现当b≤时max{a，b}≤max{a，c}必成立。在b>c时可能max{a，b}≤max{a，c}，也可能max{a，b}>max{a，c}。这时我们会交换两个元素使b≤c，从而使max{a，b}≤max{a，c}一定成立。
        因此我们可以不考虑q+b_i+b_j，只考虑后边式子的大小关系:

$$\max\{p+a_i+b_i+b_j，p+a_i+a_j+b_j\}\leq \max\{p+a_j+b_j+b_i，p+a_j+a_i+b_i\}$$

        记作②。
        当②成立时，①必然也是成立的;而②不成立时交换后即可使①成立。所以可以通过②来判别是否要交换。另外可以发现②取等时，①也取等。
        将②变形

$$\max\{b_i，a_j\}+a_i+b_j\leq \max\{b_j，a_i\}+b_i+a_j$$

        移项得

$$\max\{b_i，a_j\}-b_i-a_j\leq \max\{b_j，a_i\}-a_i-b_j$$

        等价于

$$-\min\{b_i，a_j\}\leq -\min\{b_j，a_i\}$$

        即为

$$\min\{a_i，b_j\}\leq \min\{a_j，b_i\}$$

        记为③。
        为了更好地理解本题，下面给出几个概念和定理。

• [判别元素]参与相邻元素判别的因子。比如这里的min{ai，bj}和min{aj，bi}。
• [相邻子条件]可以使相邻元素在某种次序下更优的判别元素所满足的条件。如果记A=min{a_i，b_j}，B=min{a_j，b_i}，则相邻子条件为A≤B，此时i在j前更优。记相邻子条件为P(X，Y)，在判别元素X，Y满足相邻子条件(X≤Y)时为真。
• [逆序]对于一个序列A₁，A₂，A₃，…A_n，若存在i，j$(1 \leq i < j \leq n)$使得P(A_i，A_j)为假，则称A_i，A_j组成一个逆序。逆序会破坏序列的最优性。
• [相邻全局最优化原理]一个序列，其判别元素序列为A₁，A₂，A₃，…A_n。当序列不存在逆序时，序列最优。
• [等价序列转化原理]交换相邻相等元素的位置，答案不变，这时两个序列等价。

        一个两两相邻元素都满足子条件的序列不一定是最优的，因为它可能存在逆序。比如序列ABC满足A≤B，B≤C，但是A>C(一个逆序)，此时若B=C，可以进行等价变形得到ACB，此时AC违背了子条件，交换AC得到序列CAB，显然CAB是比ABC更优的序列。
        但是存在逆序并不一定使序列不最优，也就是说存在逆序的序列得到的答案可能与最优序列答案是相同的。但是没有逆序的序列一定是最优的，化为没有逆序的序列是最保险，最稳妥的做法。
        对于国王游戏，可以采用按照左右手数值乘积升序排列的做法。这是因为排序后得到的序列没有逆序。这种两两相邻元素满足子条件就可以保证全局没有逆序的性质称为传递性。国王游戏中小于号是可传递的，但本题不可以。在本题中如果A≤B，B≤C，可能有A>C的情况发生。如果只像国王游戏那样按照相邻子条件排序，得到的序列可能有逆序。
        应该设法创造一个具有传递性的排序思路。
        观察③式，发现a与b的情况可以归结为以下几种:

• 第一种:a_i < b_i且a_j > b_j，此时必有a_i≤a_j，也就是说a是升序的。
• 第二种:a_i = b_i且a_j = b_j。a与b都是不变的，③式显然成立。
• 第三种:a_i > b_i且a_j > b_j，此时必有b_j≤b_i，也就是说b是降序的。
• 第四种:a_i < b_i且a_j > b_j，③式显然成立。
• 当然还有第五种:a_i > b_i且a_j < b_j，此时③式显然不成立

        先将I组(ab)的元素。在I组中按照a升序排列，在III组中按b降序排列。可以证明这是一种可行且可传递的排序方法。可以证明它没有逆序，任取两个元素X，Y(Y在X后)，可以归结为以下六种情况来判别P(X，Y)的成立与否:

• X，Y都来自I:符合第一种情况，成立。
• X来自I，Y来自II:显然成立
• X来自I，Y来自III:符合第四种，成立。
• X来自II，Y来自II:这时两者是相等的，成立。
• X来自II，Y来自III:显然成立。
• X来自III，Y来自III:符合第三种，成立。

        这样就找到了一种排序策略得到一个满足全局最优化原理的序列，从中找到的答案必然为最优解。
        通过这个题，可以发现相邻交换法并不只是按照相邻子条件排序就可以的，排序后的序列不能只让两两相邻元素符合子条件，还要没有逆序。这是相邻交换法的重要理论依据。
        另一个值得注意的是，虽然a=b时可以任意排序(依据等价序列转化原理)，但是不能在重载时直接返回一个true或者false，这样会出现矛盾(a < b且b < a)造成RE。示例代码中把它归到了I组中。

#include<iostream>
#include <algorithm>

using namespace std;

struct node {
    long long a, b;
    int d;

    void make(long long x, long long y) {
        a = x, b = y;
        if (a == b)d = 0;
        else if (a < b)d = -1;
        else d = 1;
    }

    bool operator<(node p) {
        if (this->d != p.d)return this->d < p.d;
        if (this->d <= 0)return this->a < p.a;
        else return this->b > p.b;
    }
} op[20001];

long long c[20001];
int n;

int main() {
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            long long x, y;
            cin >> x >> y;
            op[i].make(x, y);
        }
        sort(op + 1, op + n + 1);
        long long ans = c[1] = op[1].a + op[1].b, temp = op[1].a;
        for (int i = 2; i <= n; i++) {
            temp += op[i].a;
            c[i] = max(c[i - 1], temp) + op[i].b;
            ans = max(ans, c[i]);
        }
        cout << ans << endl;
    }
    return 0;
}