洛谷$P$2123 皇后游戏贪心

佚名 6年前 (2019-05-11) 随笔 754人围观抢沙发百度已收录

正解:贪心

解题报告:

传送门!

心血来潮打算把$luogu$提高历练地及其之前的所有专题都打通关,,,$so$可能会写一些比较水的题目的题解$QAQ$

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

这种题,显然就套路地考虑交换相邻两个人的次序的影响嘛

瞎写下式子,大概是长这样儿(就只考虑更大的那个$C$了昂$QwQ$)

$\left\{\begin{matrix}
max(max(C,A+a_{x})+b_{x},A+a_{x}+a_{y})+b_{y}\\
max(max(C,A+a_{y})+b_{y},A+a_{y}+a_{x})+b_{x}
\end{matrix}\right.$

注意,其实这个是可以化简的,就把外面的给放进去,变成这样儿

$\left\{\begin{matrix}
max(C+b_{x}+b_{y},A+a_{x}+b_{x}+b_{y},A+a_{x}+a_{y}+b_{y})\\
max(C+b_{y}+b_{x},A+a_{y}+b_{y}+b_{x},A+a_{y}+a_{x}+b_{x})
\end{matrix}\right.$

如果现在是要$x$在$y$的前面,则有

$max(C+b_{x}+b_{y},A+a_{x}+b_{x}+b_{y},A+a_{x}+a_{y}+b_{y})\leq max(C
+b_{y}+b_{x},A+a_{y}+b_{y}+b_{x},A+a_{y}+a_{x}+b_{x})$

再设一个$sum_{a}$表示$a_{x}+a_{y}$,$sum_{b}$表示$b_{x}+b_{y}$

原来那个式子就差不多长成这样儿了:

$max(C+sum_{b},A+a_{x}+sum_{b},A+sum_{a}+b_{y})\leq max(C+sum_{b},A
+a_{y}+sum_{b},A+sum_{a}+b_{x})$

显然有$C\leq A+a_{x}$是可以被直接消掉的(过于显然不想证了,,,如果有问题在下面
留言我再随便口胡下证明趴$QAQ$),所以式子又可以变成

$max(A+a_{x}+sum_{b},A+sum_{a}+b_{y})\leq max(A+a_{y}+sum_{b},A+sum_
{a}+b_{x})$

于是显然$A$就可以被消掉了,就变成了

$max(a_{x}+sum_{b},sum_{a}+b_{y})\leq max(a_{y}+sum_{b},sum_{a}+b_{x})$

再又展开得

$max(a_{x}+b_{x}+b_{y},a_{x}+a_{y}+b_{y})\leq max(a_{y}+b_{x}+b_
{y},a_{x}+a_{y}+b_{x})$

把一些东西又提出来得

$max(b_{x},a_{y})+a_{x}+b_{y}\leq max(b_{y},a_{x})+a_{y}+b_{x}$

考虑大力分类讨论$bushi$(其实在这儿的时候大力分类讨论就已经能做出来辣,,,?只是
贼麻烦$QwQ$

考虑继续移项

$max(b_{x},a_{y})-a_{y}-b_{x}\leq max(b_{y},a_{x})-b_{y}-a_{x}$

$-min(b_{x},a_{y})\leq -min(b_{y},a_{x})$

于是终于得出了最后的结论

$min(b_{x},a_{y})\geq min(b_{y},a_{x})$

然而你以为到这儿就完了嘛$QAQ$

$naive$,紫题还是麻油那么好评的鸭$QwQ$

我先放个数据:

```
3
7 3
1 1
1 6

3
1 1
1 6
7 3
```

显然我只是调换了一下大臣们的站位而已的$QwQ$

但是如果直接按那样子排序然后直接算出来$C$,输出会不一样,,,

为什么呢,仔细思考一下,发现是因为满足$min(b_{x},a_{y})\geq min(b_{y},a_{x}
)$的排序方式其实有很多(比如上面两个就都是的$QwQ$

然后在实际计算的过程中,前一个会是:$C_{1}=10\ C_{2}=11\ C_{3}=17$

后一个则是:$C_{1}=2\ C_{2}=8\ C_{3}=12$

简单来说,这个比较不具有传递性,就是这个结论只能适用于相邻两个数之间的比较,当
拓展到多个数时就会$GG$了(具体证明看这个趴,,,太神了没看太懂$TT$

当然这个结论在$min(b_{x},a_{y})\neq min(b_{y},a_{x})$的情况下还是$AC$的,
只是要考虑当$min(b_{x},a_{y})=min(b_{y},a_{x})$的时候要怎么比较

不难想到就,直接对$a$从小到大排就好鸭$QwQ$

然后就做完辣!

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
#define gc getchar()
#define ri register int
#define rb register bool
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)

const int N=20000+10;
struct node{int x,y;}nod[N];

il int read()
{
    rc ch=gc;ri x=0;rb y=1;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
    if(ch=='-')ch=gc,y=0;
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
    return y?x:-x;
}
il bool cmp(node gd,node gs){return min(gd.x,gs.y)!=min(gd.y,gs.x)?min(gd.x,gs.y)<min(gd.y,gs.x):gd.x<gs.x;}

main()
{
    int T=read();
    while(T--)
    {
        ri n=read();rp(i,1,n)nod[i]=(node){read(),read()};sort(nod+1,nod+1+n,cmp);
        ri as=nod[1].x+nod[1].y,sum=nod[1].x;
        rp(i,2,n)
        {
            sum+=nod[i].x;as=max(as,sum)+nod[i].y;
        }
        printf("%lld\n",as);
    }
}