P2123 皇后游戏
斯德哥尔摩
2018-10-14 20:20:28
[P2123 皇后游戏](https://www.luogu.org/problemnew/show/P2123)
这个题很显然贪心一下就好。
关键是怎么贪心对吧。。。
遇到这种题有一个常见套路：比较相邻两位$i,i+1$。
最简单的题：[P1223 排队接水](https://www.luogu.org/problemnew/show/P1223)
可以一眼看出排序的方式。
但是对于这种题可能我们并不能一眼看出怎么排序。
所以回到最原始的方法——推式子。
假设我们正在比较$i,i+1$两位。
我假码假码地假设交换$i$和$i+1$不会使答案更优。
我们注意到$\forall i\in[1,n-1]$，都有：$c_i\le c_{i+1}$。
设$j=i+1$，$c=c_{i-1}$，$s=\sum_{k=1}^{i-1}a_k$
则：
$$\left.\begin{array}{}&\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\end{array}\right.$$
化简：
$$\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)$$
可以发现，大概应该和$a$与$b$的大小关系有关，也就是$a_i$和$b_i$哪个大。
还有，要使一个数排在前面，那么$a$越小越好，$b$越大越好。
我们先按$a$与$b$的大小关系把所有数据分为三大组，然后开始讨论：
1. 当$a_i<b_i,a_j<b_j$时，$a_i\leq a_j$，应该按$a$升序排序。
2. 当$a_i==b_i,a_j==b_j$时，~~爱怎么排怎么排~~可以不用排。
3. 当$a_i>b_i,a_j>b_j$时，$b_i\geq b_j$，应该按b降序排序。
那么这三大组之间应该怎样排序呢？
$1$组和$2$组，$1$组在$2$组前肯定能保证满足条件。
$2$组和$3$组，$2$组在$3$组前面肯定能保证满足条件。
那么$1$组在前，$2$组在中，$3$组在后，是肯定能保证满足要求的。
我们设一个$f_i=\frac{a_i-b_i}{|a_i-b_i|}$，那么有：
$$f_i=\left\{\begin{array}{}-1&\quad&a_i<b_i\\0&\quad&a_i==b_i\\1&\quad&a_i>b_i\end{array}\right.$$
于是我们得到了最终的排序条件：
首先按$f$值排序。
然后若有$f<=0$，按$a$升序排序，这里把$2$组归入$1$组；否则有$f>0$，按$b$降序排序。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 20010
using namespace std;
int n;
long long sum[MAXN];
struct node{
long long x,y;
int f;
friend bool operator <(const node &p,const node &q){
if(p.f==q.f){
if(p.f<=0)return p.x<q.x;
return p.y>q.y;
}
return p.f<q.f;
}
}a[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
long long s=0;
sum[0]=0;
for(int i=1;i<=n;i++){
s+=a[i].x;
sum[i]=max(sum[i-1],s)+a[i].y;
}
printf("%lld\n",sum[n]);
}
void init(){
n=read();
sum[0]=0;
for(int i=1;i<=n;i++){
a[i].x=read();a[i].y=read();
if(a[i].x>a[i].y)a[i].f=1;
else if(a[i].x<a[i].y)a[i].f=-1;
else a[i].f=0;
}
sort(a+1,a+n+1);
}
int main(){
int t=read();
while(t--){
init();
work();
}
return 0;
}
```