P2123 皇后游戏 / [USACO12JAN] Mountain Climbing S / P1248 加工生产调度
先来看 P2123。我们把这个特别重要的公式打出来：
\[c_{i} = \begin{cases} a_{1}+b_{1} & ,i=1 \\ \displaystyle \max \left \{ c_{i-1},\sum_{j=1}^{i}a_{j} \right \} +b_{i} & ,2\leq i \leq n \end{cases} \]有了国王游戏的经验，我们尝试找到一个通用的排序公式。
发现本题中的 \(c_i\) 应该是递增的，也就是 \(c_{i+1}\ge c_i\)。
设当前位置为 \(i\)，\(\sum_{k=1}^{i-1}a_k\) 为 \(x\)，上一位的答案为 \(m\)，令 \(i+1=j\)。则：
\[\begin{aligned} \mathit{res}_1&=\max(\max(m,x+a_i)+b_i,x+a_i+a_j)+b_j~;\\ \mathit{res}_2&=\max(\max(m,x+a_j)+b_j,x+a_j+a_i)+b_i~. \end{aligned} \]化为：
\[\begin{aligned} \mathit{res}_1&=\max(m+b_i,x+a_i+b_i,x+a_i+a_j)+b_j~;\\ \mathit{res}_2&=\max(m+b_i,x+a_j+b_j,x+a_i+a_j)+b_i~. \end{aligned} \]遇到瓶颈。但是我们可以证明，\(m+b_i\) 可以消去。具体就不证了，前人之述备矣。消去 \(m+b_i\)，再消去 \(x\)，化为：
\[\begin{aligned} \mathit{res}_1&=\max(a_i+b_i,a_i+a_j)+b_j~;\\ \mathit{res}_2&=\max(a_j+b_j,a_i+a_j)+b_i~. \end{aligned} \]提出 \(a_i\)、\(a_j\)：
\[\begin{aligned} \mathit{res}_1&=\max(b_i,a_j)+a_i+b_j~;\\ \mathit{res}_2&=\max(b_j,a_i)+a_j+b_i~. \end{aligned} \]若不交换更优，即 \(\mathit{res}_1<\mathit{res}_2\)，则：
\[\max(b_i,a_j)+a_i+b_j<\max(b_j,a_i)+a_j+b_i~. \]移项，得：
\[\max(b_i,a_j)-a_j-b_i<\max(b_j,a_i)-a_i-b_j~. \]稍微想想，就能得到：
\[-\min(b_i,a_j)<-\min(b_j,a_i)~. \]即：
\[\min(b_i,a_j)>\min(b_j,a_i)~. \]酣畅淋漓。
这个不等式实际上就是 Johnson 不等式，用于解决流水调度问题。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
using ll=long long;
constexpr int MAXN=2e4+5;
int T,n;
int min(int a,int b){
return a<b?a:b;
}
ll max(ll a,ll b){
return a>b?a:b;
}
struct P{
int a,b;
bool operator<(const P&x)const{
return min(b,x.a)>min(x.b,a);
}
}p[MAXN];
int main(){
T=read();
while(T--){
n=read();
for(int i=1;i<=n;++i) p[i]={read(),read()};
sort(p+1,p+n+1);
ll res=p[1].a+p[1].b,sm=p[1].a,lst=res;
for(int i=2;i<=n;++i){
sm+=p[i].a;
res=max(res,lst=max(lst,sm)+p[i].b);
}
write(res);
}
return fw,0;
}
你是不是以为这样就 AC 了？然后你就会发现你得到了高贵的 80pts。
伪在哪里？伪在排序的不稳定性。你会发现上述的排序方法会漏掉很多情况，不能准确地排序。比如，最基本的传递性都不能保证。
排序的传递性：若 \(a<b\land b<c\)，则 \(a<c\)。
此时有两种解决方法：
- 掺点随机化，在时间允许的范围内多排序几次。
- 想办法完善刚才的排序式子。
方法 1 虽好，但也让我们和最优解失之交臂。我们还是来看方法 2。
回顾刚才的排序式子：
\[\min(b_i,a_j)>\min(b_j,a_i)~. \]要使一个数排在前面，则 \(a\) 越小越好，\(b\) 越大越好。这句话不是我说的，是题解说的。
我们把所有数对分成三大组：
- 当 \(a_i<b_i\land a_j<b_j\) 时，则 \(a_i\le a_j\)，应该按 \(a\) 升序排序；
- 当 \(a_i=b_i\land a_j=b_j\) 时，随便排；
- 当 \(a_i>b_i\land a_j>b_j\) 时，则 \(b_i\ge b_j\)，应该按 \(b\) 降序排序。
然后考虑这三大组之间的排序关系。发现 1 组在前、2 组在中、3 组在右的原则是能保证答案的，于是令
\[d_i=\begin{cases}1&a_i>a_j\\0&a_i=a_j\\-1&a_i<a_j\end{cases}~,\quad\text{即 }d_i=\operatorname{sgn}(a_i-a_j)~. \]由此得到最终的排序条件：先按 \(d\) 值排序，然后若 \(d\le0\)，把 \(a\) 升序排序（这里将 2 组归为 1 组）；否则把 \(b\) 降序排序。
完美。
#include<bits/stdc++.h>
#define fw fwrite(obuf,p3-obuf,1,stdout)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#define putchar(x) (p3-obuf<1<<20?(*p3++=(x)):(fw,p3=obuf,*p3++=(x)))
using namespace std;
char buf[1<<20],obuf[1<<20],*p1=buf,*p2=buf,*p3=obuf,str[20<<2];
int read(){
int x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x;
}
template<typename T>
void write(T x,char sf='\n'){
if(x<0)putchar('-'),x=~x+1;
int top=0;
do str[top++]=x%10,x/=10;while(x);
while(top)putchar(str[--top]+48);
if(sf^'#')putchar(sf);
}
using ll=long long;
constexpr int MAXN=2e4+5;
int T,n;
int min(int a,int b){
return a<b?a:b;
}
ll max(ll a,ll b){
return a>b?a:b;
}
struct P{
int a,b,d;
bool operator<(const P&x)const{
if(d^x.d) return d<x.d;
if(d^1) return a<x.a;
return b>x.b;
}
}p[MAXN];
int main(){
T=read();
while(T--){
n=read();
for(int i=1;i<=n;++i){
p[i]={read(),read()};
p[i].d=p[i].a>p[i].b?1:p[i].a<p[i].b?-1:0;
}
sort(p+1,p+n+1);
ll res=p[1].a+p[1].b,sm=p[1].a,lst=res;
for(int i=2;i<=n;++i){
sm+=p[i].a;
res=max(res,lst=max(lst,sm)+p[i].b);
}
write(res);
}
return fw,0;
}
至于剩下的两道题，完全可以看作本题的三倍经验。因为 Johnson 不等式本就是用于解决流水调度问题，这两道题反而更加简单。
对于 USACO 的那道题，显然总耗时由以下两个因素决定：还未上山的奶牛需要上山，以及上了山的奶牛需要下山。我们的目标是让山上等待下山的奶牛序列不间断，这样就节省了时间，故上山快的奶牛需要先上山。同理，为了让下山序列连续，下山慢的奶牛需要先下山。然后就会发现和上文推出的 Johnson 不等式是一样的。
对于 P1248 更是同理。
标签：Mountain,aligned,res,mathit,P1248,题解,int,max,排序 From： https://www.cnblogs.com/laoshan-plus/p/18538380