索引

算法简介算法框架一道例题题目DescriptionInputOutputSample InputSample OutputHint分析标程1算法优化优化后标程提示 注意 另一道例题题目DescriptionInputOutputSample Input1Sample Output1Sample Input2Sample Output2分析标程（70分）hack数据Input假标程Output 严格弱序为何错误严格弱序的证明正确解法正解 总结

算法简介

邻项交换排序是竞赛中一种常用、易掌握的贪心策略，用于解决安排顺序一类问题；但是，这同时也是一个易错的算法，若在比赛不注意细节，很容易使贪心策略错误。

算法框架

邻项交换排序的思路大致如下

1、从头开始验证相邻是否满足最优子结构，若不是，交换相邻两项 2、重复执行1至每相邻两项均为最优子结构

一道例题

题目

[NOIP2012]提高组D1T2 国王游戏

Description

恰逢 H 国国庆，国王邀请 $n$ 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 $n$ 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

Input

第一行包含一个整数 $n$，表示大臣的人数。 第二行包含两个整数$a$和$b$，之间用一个空格隔开，分别表示国王左手和右手上的整数。 接下来 $n$ 行，每行包含两个整数 $a$ 和 $b$，之间用一个空格隔开，分别表示每个大臣左手和右手上的整数。

Output

一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。

Sample Input

3 1 1 2 3 7 4 4 6

Sample Output

2

Hint

【输入输出样例说明】 按 1、2、3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2； 按 1、3、2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2； 按 2、1、3 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2； 按 2、3、1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9； 按 3、1、2 这样排列队伍，获得奖赏最多的大臣所获得金币数为 2； 按 3、2、1 这样排列队伍，获得奖赏最多的大臣所获得金币数为 9。 因此，奖赏最多的大臣最少获得 2 个金币，答案输出 2。

【数据范围】 对于 20%的数据，有 $1\le n\le 10,0<a,b<8$； 对于 40%的数据，有 $1\le n\le 20,0<a,b<8$； 对于 60%的数据，有 $1\le n\le 100$； 对于 60%的数据，保证答案不超过 $10^9$； 对于 100%的数据，有$1\le n\le 1000,0<a,b<10000$。

分析

首先，不难发现，交换相邻两个数对前后均无影响 设$w[i]$为第$i$个大臣获得金币数 $l[0],r[0]$为国王左右手，$l[1...n],r[1...n]$为n个大臣左右手 设$i,j$，且$i,j$相邻。$i,j$前所有大臣（包括国王）左手数字之和为$k$ 这两个中最大值 $maxk=max\{\frac{k}{r[i]},\frac{k\ast l[i]}{r[j]}\};$ 若交换i,j大臣最大值则为 $maxk=max\{\frac{k\ast l[j]}{r[i]},\frac{k}{r[j]}\};$ 依照贪心思想，maxk 变小，最终就不会变差，且可能更优，所以i在j前面的条件是$$max\{\frac{k}{r[i]},\frac{k\ast l[i]}{r[j]}\}\le max\{\frac{k\ast l[j]}{r[i]},\frac{k}{r[j]}\}$$ 因为$k\ge 1$ 所以$\frac{k\ast l[i]}{r[j]}\ge \frac{k}{r[j]}$ && $\frac{k\ast l[j]}{r[i]}\ge \frac{k}{r[i]}$ 所以只需证明$\frac{k\ast l[i]}{r[j]}\le \frac{k\ast l[j]}{r[i]}$ 化简得$$l[i]\ast r[i]\le l[j]\ast r[j]$$ 若找到邻项不满足条件该条件则交换i,j两项

标程1

#include<bits/stdc++.h> using namespace std; long long l[1005],r[1005]; int main() { int n; scanf("%d",&n); for(int i = 0;i <= n;i++) scanf("%lld%lld",l+i,r+i); for(int i = 1;i < n;i++) for(int j = 1;j <= n-i;j++) if(l[j]*r[j] > l[j+1]*r[j+1]) swap(l[j],l[j+1]),swap(r[j],r[j+1]); long long k = l[0],ans = 0; for(int i = 1;i <= n;i++) { ans = max(ans,k/r[i]); k *= l[i]; } printf("%lld",ans); return 0; }

算法优化

这个程序时间复杂度为$O(n^2)$，效率的瓶颈在排序，一个冒泡排序的算法很难满足OI中的效率要求，所以我们想到用快排的方法优化算法

优化后标程

#include<bits/stdc++.h> using namespace std; struct kkk { int l;int r; bool operator < (const kkk &other) const { return l * r < other.l * other.r; } }a[1005]; int main() { int n; scanf("%d",&n); for(int i = 0;i <= n;i++) scanf("%lld%lld",&a[i].l,&a[i].r); sort(a+1,a+n+1); long long k = a[0].l,ans = 0; for(int i = 1;i <= n;i++) { ans = max(ans,k/a[i].r); k *= a[i].l; } printf("%lld",ans); return 0; }

提示

这个代码在OJ上只能得60分，满分代码需用高精，然鹅这显然不在我要讲的范围内

注意

将排序方式从冒泡排序改为快速排序并不一定正确，这个问题在下一个例题中具体讨论。

另一道例题

题目

皇后游戏（国王游戏的升级版）

Description

皇后有 n 位大臣，每位大臣的左右手上面分别写上了一个正整数。恰逢国庆节来临，皇后决定为 n 位大臣颁发奖金，其中第 i 位大臣所获得的奖金数目为第i－1 位大臣所获得奖金数目与前 i 位大臣左手上的数的和的较大值再加上第 i 位大臣右手上的数。 形式化地讲：我们设第 i 位大臣左手上的正整数为 a_i，右手上的正整数为 b_i，则第 i 位大臣获得的奖金数目为 ci可以表达为： $$c_i=\{\begin{array}{ll}{a}_1+b_1,& \text{if }i\text{ = 1}\\ max\{c_{i-1},{\sum }_{j=1}^i{a}_j\}+b_i,& \text{if }2\le i\le n\end{array}$$ 当然，吝啬的皇后并不希望太多的奖金被发给大臣，所以她想请你来重新安排一下队伍的顺序，使得获得奖金最多的大臣，所获奖金数目尽可能的少。 注意：重新安排队伍并不意味着一定要打乱顺序，我们允许不改变任何一位大臣的位置。

Input

第一行包含一个正整数 T，表示测试数据的组数。 接下来 T 个部分，每个部分的第一行包含一个正整数 n，表示大臣的数目。 每个部分接下来 n 行中，每行两个正整数，分别为 a_i和 b_i，含义如上文所述。

Output

共 T 行，每行包含一个整数，表示获得奖金最多的大臣所获得的奖金数目。

Sample Input1

1 3 4 1 2 2 1 2

Sample Output1

8

Sample Input2

2 5 85 100 95 99 76 87 60 97 79 85 12 9 68 18 45 52 61 39 83 63 67 45 99 52 54 82 100 23 54 99 94 63 100 52 68

Sample Output2

528 902

分析

与上题类似，我们此题仍然先考虑相邻两项$i,j$ 先考虑交换$i,j$对前后的影响 若交换$i,j$使$max\{w_i,w_j\}$变小：$i,j$前的元素不受影响，$i,j$后的元素情况不会变差，且可能产生更好情况 所以此题可以用邻项交换排序来解决 现在讨论我们比较的方式,设$k={\sum }_p^{min\{i,j\}-1}{a}_p;$$i,j前一位大臣的收益为pre$ 因为$b_i$为正数，所以$c_i$单调递增 若$i$在$j$前，$max\{w_i,w_j\}=w_j=max\{k+a_i+a_j,max\{pre,k+a_i\}+b_i\}+b_j$ 若$j$在$i$前，$max\{w_i,w_j\}=w_i=max\{k+a_j+a_i,max\{pre,k+a_j\}+b_j\}+b_i$ 所以$i$在$j$前的条件为 $$max\{k+a_i+a_j,max\{pre,k+a_i\}+b_i\}+b_j<max\{k+a_j+a_j,max\{pre,k+a_j\}+b_j\}+b_i$$ 因为$max\{x,y\}+z=max\{x+z,y+z\}$ 所以不等式左右两边化为$max\{k+a_i+a_j+b_j,pre+b_i+b_j,k+a_i+b_i+b_j\}$和$max\{k+a_i+a_j+b_i,pre+b_i+b_j,k+a_j+b_i+b_j\}$ 因为两边都有$pre+b_i+b_j$所以需要比较的元素是$max\{k+a_i+a_j+b_j,k+b_i+b_j+a_i\}$和$max\{k+a_i+a_j+b_i,k+b_i+b_j+a_j\}$两边同减去$k+a_i+a_j+b_i+b_j$并化简得到 $$min\{a_j,b_i\}>min\{a_i,b_j\}$$ 利用这个结论，我们可以写出下面这个假标程 标程

标程（70分）

#include<bits/stdc++.h> using namespace std; struct kkk { int l,r; bool operator < (const kkk &other) const { return min(l,other.r) < min(r,other.l); } }a[20005]; int main() { int T; cin>>T; while(T--) { int n; cin>>n; for(int i = 0;i < n;i++) cin>>a[i].l>>a[i].r; sort(a,a+n); int sum = 0,ans = 0; for(int i = 0;i < n;i++) { sum += a[i].l; ans = max(ans,sum) + a[i].r; } cout<<ans<<endl; } return 0; }

但是，这个程序叫上去会有部分点WA，下面提供一组hack数据

hack数据

Input

2 4 1 1 1 1 3 5 2 7 4 1 1 3 5 2 7

假标程Output

16 17

但是我们发现，这两组数据只有大臣的顺序是不同的 如果我们输出排序后的结果，则是

1 1 1 1 2 7 3 5

和

1 1 3 5 1 1 2 7

为什么会这样，我们得先了解严格弱序

严格弱序

而 C++ 标准库要求用于排序的运算符必须满足严格弱序,下面是The c++ standard library对严格弱序的描述：

(1)It has to be antisymmetric.   This means that for operator <: If x<y is true, then y<x is false.   This means that for a predicate op(): If op(x,y) is true, then op(y,x) is false. (2)It has to be transitive.   This means that for operator <: If x<y is true and y<z is true, then x<z is true.   This means that for a predicate op(): If op(x,y) is true and op(y,z) is true, then op(x,z)is true. (3)It has to be irreflexive.   This means that for operator <: x<x is always false.   This means that for a predicate op(): op(x,x) is always false. (4)It has to have transitivity of equivalence,   which means roughly: If a is equivalent to b and b is equivalent to c, then a is equivalent to c.   This means that for operator <: If !(a<b)&&!(b<a) is true and !(b<c)&&!(c<b) is true.then !(a<c)&&!(c<a) is true.   This means that for a predicate op(): If op(a,b), op(b,a), op(b,c), and op(c,b) all yield.false, then op(a,c) and op(c,a) yield false.

为何错误

根据定义，简单的说就是我们上述比较命题没有严格弱序的特征——它不满足上述定义中的传递性 也就是说根据$min\{a_i,b_j\}<min\{a_j,b_i\}$和$min\{a_j,b_k\}<min\{a_k,b_j\}$不能推出$min\{a_i,b_k\}<min\{a_k,b_i\}$ 反例应该很好举吧

严格弱序的证明

由于证明较为复杂，蒟蒻不太懂，详见大佬博客

正确解法

观察不等式$min\{a_j,b_i\}>min\{a_i,b_j\}$我们发现$i$若在$j$前面，则$a_i$越小越好，$a_j$越大越好 这样，我们想到来讨论$a_i$和$b_i$的大小关系，我们将这些数据分为三组： （1）$a_i<b_i\&\&a_j<b_j$    按$a$的升序排列即可 （2）$a_i=b_i\&\&a_j=b_j$    怎么排都无所谓 （3）$a_i>b_i\&\&a_j>b_j$    按$b$的降序排列即可 组与组间又没有确定的大小关系呢 先取（1）（2）组元素进行比较设$i$为第一组元素,$j$为第二组元素 比较对象为$min\{a_j,b_i\}$和$min\{a_i,b_j\}$ 将上述条件带入该式得到$min\{a_j,b_i\}\ge min\{a_i,b_j\}$ 所以第一组元素在第二组元素前 同理可得第二组元素在第一组元素前 这样就可以得到我们的满分代码

正解

#include<bits/stdc++.h> using namespace std; struct kkk { int l,r,k,num; bool operator < (const kkk &other) const { if(k != other.k) return k < other.k; else if(k <= 0) return l < other.l; else return r > other.r; } }a[20005]; int main() { int T; cin>>T; while(T--) { int n; cin>>n; for(int i = 0;i < n;i++) cin>>a[i].l; for(int i = 0;i < n;i++) { cin>>a[i].r; a[i].num = i+1; if(a[i].l == a[i].r) a[i].k = 0; else if(a[i].l < a[i].r) a[i].k = -1; else a[i].k = 1; } sort(a,a+n); long long sum = 0,ans = 0; for(int i = 0;i < n;i++) { sum += a[i].l; ans = max(ans,sum) + a[i].r; } cout<<ans<<endl; for(int i = 0;i < n;i++) cout<<a[i].num<<' '; } return 0; }

总结

（1）在可以通过比较相邻两项得出交换或不交换一定不会更差时，可以通过邻项交换排序的方式来得到最优解。

（2）邻项交换排序的比较函数需要满足严格弱序，并且排序完成后任意交换相邻元素都不会更优。

（3）使用这种算法时，一定要注意以上两点，才能得到真正正确的算法。