题解 P2123 【皇后游戏】

· · 题解

前置链接

P1080 国王游戏（如果没过的话建议先过）

P2123 皇后游戏（本题）

大佬的题解（如果需要深入了解和更多知识）

一，目标：最后的大臣

这是一个困难的任务，但无论如何，皇后请我们去解决问题，我们应该全力以赴，说不定省下的钱可以分一点~~

让我们观察一下奖金的表达式：

c_{i}= \begin{cases} a_{1}+b_{1}, & \ i=1 \\ \max \left \{ c_{i-1},\sum_{j=1}^{i}a_{j} \right \}+b_{i}, & \ 2\leq i \leq n \end{cases}

有

c_i=\max \{ c_{i-1},\sum_{j=1}^{i}a_{j} \}+b_i \geqslant c_{i-1}+b_i > c_{i-1}

这说明，排得越靠后的大臣得到的奖金越多。

由此可以知道得到奖金最多的大臣就是排最后的大臣，而皇后需要得到奖金最多的大臣的到的奖金尽量少，所以我们需要让排最后的大臣尽量少得奖金。

二，两个人间的选择

让我们从简单的情况开始吧。

现在假设一位不愿留下姓名的智者已经帮我们把前面的队伍排好了，只剩下两位大臣伊凡（Ivan）和杰克（Jack）在等待中了。我们就叫他们 i 和 j 好了。

两位大臣都想站在最后以获得最多的奖金，但皇后有她的心思。

当 i 站在 j 前时队伍是这样的(前面队伍的最后一个人是萨姆Sam,称为 s ）：

大臣 1 2 ... s i j
左手 a_1 a_2 ... a_s a_i a_j
右手 b_1 b_2 ... b_s b_i b_j
奖金 c_1 c_2 ... c_s c_i c_j

设

S=a_1+a_2+...+a_s=\sum_{k=1}^s a_k

此时 i 得到的奖金为

c_{i,1}=\max(c_s,S+a_i)+b_i $ C_1=c_{j,1}=\max(c_{i,1},S+a_i+a_j)+b_j

C_1为我们将 i 排前面时发出的最多奖金。

如果将他们两个交换位置，那么同理我们可以得到我们将 j 排前面时发出的最多奖金为C_2=c_{i,2}=\max(c_{j,2},S+a_i+a_j)+b_i

( c_{j,2}=\max(c_s,S+a_j)+b_j )

现在我们比较一下 C_1 和 C_2 ：

C_1=\max(\max(c_s,S+a_i)+b_i,S+a_i+a_j)+b_j C_2=\max(\max(c_s,S+a_j)+b_j,S+a_i+a_j)+b_i

嗯。。。有些惨不忍睹。

在下一步处理前你要先看一下这几个式子（都很显然）

\max(p,q)+r=\max(p+r,q+r) \max(\max(p,q),r)=\max(p,q,r)

就这样我们得到了：

C_1=\max(c_s+b_i+b_j,S+a_i+b_i+b_j,S+a_i+a_j+b_j) C_2=\max(c_s+b_i+b_j,S+a_j+b_i+b_j,S+a_i+a_j+b_i)

冷静一下，让我们来仔细观察一下这两个式子。

很容易发现两边都有（c_s+b_i+b_j）这个部分。

那么设

P=c_s+b_i+b_j Q=\max(S+a_i+b_i+b_j,S+a_i+a_j+b_j) R=\max(S+a_j+b_i+b_j,S+a_i+a_j+b_i)

有

C_1=\max(P,Q) C_2=\max(P,R)

看上去好多了，不是吗？

要比较两者，先关注不同的部分 Q 和 R 。

我们请皇后叫一个计算师来计算一下这两个值。

“报告，经计算，Q不大于R。”（这怎么算的，把计算师拖下去。。。）

那么，已知 Q \leqslant R ,如何比较 C_1 和 C_2 呢？

其实有：Q \leqslant R \Rightarrow \max(P,Q)\leqslant\max(P,R)即C_1 \leqslant C_2

如何证明？

若 P \leqslant Q \leqslant R ,则 \max(P,Q)=Q \leqslant R=\max(P,R)

若 Q \leqslant P \leqslant R ,则 \max(P,Q)=P \leqslant R=\max(P,R)

若 Q \leqslant R \leqslant P ,则 \max(P,Q)=P=\max(P,R)

很好，梳理一下，由我们得知 Q \leqslant R ,可得到 C_1 \leqslant C_2，即表明如果我们让 i 站在 j 前，发出的最多奖金将会更少。

通知皇后将伊凡排在杰克前，大功告成。

三，更深入的准则

刚才我们分析了最后两个人的情况，并得到了一个结论（即比较 Q 和 R )，但事实上我们需要解决的是整个大臣群体的排队问题，我们需要继续研究之前的结论来获得更多的启示。

$$\max(S+a_i+b_i+b_j,S+a_i+a_j+b_j) \leqslant \max(S+a_j+b_i+b_j,S+a_i+a_j+b_i)$$ 根据之前的那个显然的式子，有 $$\max(b_i,a_j)+S+a_i+b_j \leqslant \max(b_j,a_i)+S+a_j+b_i$$ $$a_i+b_j-\max(a_i,b_j) \leqslant a_j+b_i-\max(a_j,b_i)$$ 不等号左边的意思是 $a_i$ 和 $b_j$ 的和减去二者中较大的那个，这会使较小的那个留下，等价于 $\min(a_i,b_j)$ ，同理右边等价于 $\min(a_j,b_i)$ 。 $$\min(a_i,b_j) \leqslant \min(a_j,b_i)$$ 这即是我们需要的重要准则。它表明： **1.对于两个大臣 $i$ 和 $j$ ，我们需比较 $\min(a_i,b_j)$ 和 $\min(a_j,b_i)$ ，若 $\min(a_i,b_j) \leqslant \min(a_j,b_i)$ ，那将 $i$ 排在 $j$ 前可使靠后一个人得到的奖金尽可能少。** **2.这不受他们前面和后面的大臣的影响。** 在另一方面，我们再看一次这个式子：$c_i=\max \{ c_{i-1},\sum_{j=1}^{i}a_{j} \}+b_i

对于任何一个大臣，改变他前方大臣的排序不会影响到 \sum_{j=1}^{i}a_{j}的大小 (a+b+c=b+a+c)，而如果 c_{i-1} 变小，那 c_i 也不会变得更大（只可能不变或变小），这对我们的最终目标：最后的大臣尽量少拿钱是有帮助的。

综上所述，我们可以将这个重要准则用于所有大臣，每一次交换位置都对我们的最终目标有利。让这个准则成为排序准则，得到一个大臣队伍序列，那应该就是答案。

但事情还没完。。。

四，不完整的准则

理想丰满，现实残酷。

皇后下命令让士兵给大臣排队，但在执行中，我们很快发现了问题：

如果 \min(a_i,b_j) = \min(a_j,b_i)，二者如何排序？

随便排吗？哦，那可会出问题的。

让我们请来 i , j ,k 三位大臣，假设他们左右手上数字的情况如下：

大臣 左手a 右手b
i 2 3
j 3 4
k 1 1

士兵先看了看 i 和 k ，\min(a_i,b_k)=\min(2,1)=1 , \min(a_k,b_i)=\min(1,3)=1 。

“好吧，你们俩就随便排吧。 k 就排 i 前面吧。”

士兵又看了看 j 和 k , \min(a_j,b_k)=\min(3,1)=1 , \min(a_k,b_j)=\min(1,j)=1 。

“也是无所谓。 j 就排 k 前面吧。”

现在的情况（越向下越靠前）：

大臣 左手a 右手b 奖赏c
j 3 4 7
k 1 1 8
i 2 3 11

但，细心的你一定已经发现了：\min(a_i,b_j)=\min(2,4)=2<\min(a_j,b_i)=\min(3,3)=3

这表明， i 应该在 j 前，如果我们交换 i 和 j ,那结果是：

大臣 左手a 右手b 奖赏c
i 2 3 5
k 1 1 6
j 3 4 10

看到这里，皇后已经打算把那个士兵扔到海里喂鱼了。但这并不是他的错，问题出在我们的排序准则上：

i=k,j=k \nRightarrow i=j

我们需要更完整的准则。

五，解决之道

让我们去采访一下伊凡（i)吧，他正为自己排在 j 前面而生气呢。

“你对于这次排队的情况，有什么看法吗？”

“天哪，这完全是因为我左手上的数字太小，而右手上的太大了！”

就是这样，让我们再次观察一下那个重要准则：

\min(a_i,b_j) \leqslant \min(a_j,b_i)

从 i 的角度出发，他无法左右 a_j 和 b_j 的大小，于是他只关注 a_i 和 b_i ，他看到了：

a_i \leqslant b_i **重要结论：左手数字越小，右手数字越大，越应该靠前排。** 于是我们应该这样排序： **1.如果$\min(a_i,b_j) < \min(a_j,b_i)$，将 $i$ 排在 $j$ 前。** **2.如果$\min(a_i,b_j) = \min(a_j,b_i)$，将左手数字小的排前，或将右手数字大的排前。** 这样就没什么问题了。 ### 六，神奇时刻 还有另一种排序方式。 让我们把所有大臣分为三组：倒霉蛋组，普通组，幸运儿组。 #### 倒霉蛋组： 如果一个大臣左手上的数字小于右手上的数字（$a_i<b_i$)，那么他进入此组。 **对于此组的大臣，按左手上数字进行升序排序。** 这样做符合重要准则，证明如下： 已知：$a_i<b_i,a_j<b_j,a_i \leqslant a_j

证：\min(a_i,b_j) \leqslant \min(a_j,b_i)

证明：\min(a_i,b_j) \leqslant a_i，又a_i<b_i,a_i \leqslant a_j可得\min(a_i,b_j) \leqslant \min(a_j,b_i)

普通组：

如果一个大臣左手上的数字等于右手上的数字（a_i=b_i)，那么他进入此组。

对于此组的大臣，无排序规则。

此组大臣任意两人间都无法用重要准则排序，因此虽然是随便排，但是不会出现之前一样的问题。

幸运儿组：

如果一个大臣左手上的数字大于右手上的数字（a_i>b_i)，那么他进入此组。

对于此组的大臣，按右手上数字进行降序排序。

这样做也符合重要准则，证明类似倒霉蛋组。

组与组之间：

倒霉蛋组始终在前，普通组在中，幸运儿组始终在后。

这样做符合重要准则。

(假设i在倒霉蛋组，k在普通组，j在幸运儿组）

a_i<b_i,a_k=b_k \Rightarrow \min(a_i,b_k)<\min(a_k,b_i) a_j>b_j,a_k=b_k \Rightarrow \min(a_j,b_k)>\min(a_k,b_j)

事实上就是：

(P 代表普通组）

Q<R \Rightarrow \min(Q,P)<\min(P,R)

(倒霉蛋组与普通组）

Q>R \Rightarrow \min(Q,P)>\min(P,R)

（幸运儿组与普通组）

证明类似于二中的Q \leqslant R \Rightarrow \max(P,Q)\leqslant\max(P,R)。

七，代码如下

五中的方法：

#include<iostream>
#include<algorithm>
using namespace std;
struct meo
{
    int a,b;
}m[20010];//大臣们 
bool cmp(meo x,meo y)
{
    if (min(x.a,y.b)==min(x.b,y.a))
    return x.a<y.a;//或是 return x.b>y.b; 
    else
    return min(x.a,y.b)<min(x.b,y.a);
}
long long c[20010];
int main()
{
    int T,n;
    cin>>T;
    long long sum;
    for (int i=1;i<=T;++i)
    {
        cin>>n;
        for (int j=1;j<=n;++j)
        cin>>m[j].a>>m[j].b;
        sort(m+1,m+n+1,cmp);//排序部分，再下为模拟部分 
        sum=0;
        for (int j=1;j<=n;++j)
        {
            sum+=m[j].a;
            c[j]=max(c[j-1],sum)+m[j].b;
        }
        cout<<c[n]<<endl;
    }
    return 0;
}

六中的方法：

#include<iostream>
#include<algorithm>
using namespace std;
struct meo
{
    int a,b,d;//d表示组别，1=倒霉蛋，0=普通，-1=幸运儿 
}m[20010];
bool cmp(meo x,meo 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;

}
long long c[20010];
int main()
{
    int T,n;
    cin>>T;
    long long sum;
    for (int i=1;i<=T;++i)
    {
        cin>>n;
        for (int j=1;j<=n;++j)
        {
            cin>>m[j].a>>m[j].b;
            if (m[j].a<m[j].b)
            m[j].d=1;//倒霉蛋组 
            else if (m[j].a>m[j].b)
            m[j].d=-1;//幸运儿组 
            else
            m[j].d=0;//普通组
            /*
            事实上这里写成
            m[j].d=(m[j].b-m[j].a)/abs(m[j].b-m[j].a);
            会更聪明 
            */ 
        }
        sort(m+1,m+n+1,cmp);
        sum=0;
        for (int j=1;j<=n;++j)
        {
            sum+=m[j].a;
            c[j]=max(c[j-1],sum)+m[j].b;
        }
        cout<<c[n]<<endl;
    }
    return 0;
}