Johnson 法则早就该会了……
一般地，设 \(c_i\) 表示完成第 \(i\) 个后的时间,得
\[c_i=\begin{cases} a_1+b_1 &(i=1)\\ \max\left(c_{i-1},\sum\limits_{j=1}^i a_j\right)+b_i &(i>1) \end{cases}\]在调整法之前，有一个显然的结论：若 \(c_i\) 变小，其后的 \(c\) 都会变小。
之后考虑调整。令 \(T\) 表示前面数的 \(a\) 之和，\(P\) 表示 \(c_{i-1}\)
\(i\) 在前：\(\max(\max(P,T+a_i)+b_i,T+a_i+a_j)+b_j\)
\(j\) 在前：\(\max(\max(P,T+a_j)+b_j,T+a_i+a_j)+b_i\)
等价于比较
\(\max\{T+a_i+b_i+b_j,T+a_i+a_j+b_j\}\)
\(\max\{T+a_j+b_i+b_j,T+a_i+a_j+b_i\}\)
两式同减 \(T+a_i+a_j+b_i+b_j\) 得 \(\max(-a_j,-b_i)\) 与 \(\max(-a_i,b_j)\)，即 \(-\min(a_j,b_i)\) 和 \(-\min(a_i,b_j)\)
分析可知当 \(\min(a_i,b_j)\leq \min(a_j,b_i)\) 时 \(i\) 在 \(j\) 前面更优。
照着上述思路，可以写出一份能 AC P1248 的代码。
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
char buf[1<<14],*p1=buf,*p2=buf;
#define GetC() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<14,stdin),p1==p2)?EOF:*p1++)
struct Ios{}io;
template <typename _tp>
Ios &operator >>(Ios &in,_tp &x){
x=0;int w=0;char c=GetC();
for(;!isdigit(c);w|=c=='-',c=GetC());
for(;isdigit(c);x=x*10+(c^'0'),c=GetC());
if(w) x=-x;
return in;
}
const int N=1e5+5;
struct qwq{int a,b,id;}a[N];
bool operator <(qwq x,qwq y){return min(x.a,y.b)<min(y.a,x.b);}
int main(){
int n;io>>n;
for(int i=1;i<=n;++i) io>>a[i].a;
for(int i=1;i<=n;++i) io>>a[i].b,a[i].id=i;
sort(a+1,a+n+1);
long long s1=a[1].a,s2=a[1].a+a[1].b;
for(int i=2;i<=n;++i){
s1+=a[i].a;
s2=max(s2,s1)+a[i].b;
}
printf("%lld\n",s2);
for(int i=1;i<=n;++i) printf("%d%c",a[i].id," \n"[i==n]);
return 0;
}
这么做过不了P2123。
接下来的内容来自 @ouuan 浅谈邻项交换排序的应用以及需要注意的问题 一文。
hack 数据见此:
2
4
1 1
1 1
3 5
2 7
4
1 1
3 5
1 1
2 7
原因在于两次排序结果分别为
1 1
1 1
2 7
3 5
和
1 1
3 5
1 1
2 7
接下引入严格弱序这一概念。
对于一个比较运算符（用“\(<\)”表示此运算符，用“\(\not <\)”表示不满足此运算符），若满足以下四个条件，则称其是满足严格弱序的：
- \(x\not< x\)（非自反性）
- 若 \(x<y\) ，则 \(y\not <x\)（非对称性）
- 若 \(x<y,y<z\)，则 \(x<z\)（传递性）
- 若 \(x\not<y,y\not<x,y\not < z,z\not<y\)，则 \(x\not <z,z\not <x\)（不可比性的传递性）
可以证明，我们定义的 “\(<\)” 运算具有传递性，但不具有不可比性的传递性。
换句话说，可能会出现较大的数出现在前面的情况。然后就不是最优了。
所以，必须保证具有不可比性的传递性。
对 \(\min(a_i,b_j)<\min(a_j,b_i)\) 进行大力分讨，可得到以下方法：
定义 \(d_i=\begin{cases}-1 & a_i<b_i\\0 &a_i=b_i\\ 1&a_i>b_i\\\end{cases}\)
先按 \(d\) 排。对于 \(d_i=-1\) 的元素，可以按照 \(a\) 从小往大排，对于等于 \(0\) 的元素，随便排，对于 \(d_i=1\) 的元素，按照 \(b\) 从大往小排。
这玩意就叫 Johnson 法则。
标签：min,P1248,max,调度,int,P2123,cases From： https://www.cnblogs.com/pref-ctrl27/p/16971334.html