邻项交换排序类贪心

本文主要是介绍邻项交换排序类贪心，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

原理论述部分引用自浅谈邻项交换排序的应用以及需要注意的问题
luogu题单

引言

邻项交换排序是一种常见的贪心算法，通过比较两个相邻元素交换前后的优劣对整个序列进行排序，从而使得这个序列成为题目所求的最优解。
然而，邻项交换排序的应用有一些需要注意的地方，稍有不慎便会成为一个错误的算法。
简而言之，要求满足排序之后的得到的新排列唯一，或所有新排列均为最优解。
不然可能会出现求出局部而非全局最优解的情况：

如上图所示，假定这个空间为所有可能排列构成的一个排列空间，一个点对应一个排列。
再令圆上的所有排列恰巧比相邻的排列都更差。如此排序过程中排列S'就不会达到圆圈外的排列S的状态，因为任何到达S的排序方式上都会经过圆圈，即变得更差。
故S'只会在圈内寻找最优解。再假定S为最优解，则排序方式就显然错误了。具体的例子可以看皇后游戏的反例。

国王游戏

NOIP2012提高组D1T2 国王游戏

分析

考虑队伍中的两位相邻的大臣i,j（此时j在i后一位），分别用\(a_i,a_j,b_i,b_j\)表示这两位大臣左手上和右手上的数字，设这两位大臣前面的所有大臣左手上的数乘积为\(k\)。
两位大臣换序与否对前面和后面大臣均无影响，单独计算他们两人交换位置前后对答案的贡献。
i在j前面:\(max(\lfloor \frac{k}{b_i} \rfloor,\lfloor \frac{ka_i}{b_j} \rfloor)\)
j在i前面:\(max(\lfloor \frac{k}{b_j} \rfloor,\lfloor \frac{ka_j}{b_i} \rfloor)\)
当\(max(\lfloor \frac{k}{b_i} \rfloor,\lfloor \frac{ka_i}{b_j} \rfloor) <= max(\lfloor \frac{k}{b_j} \rfloor,\lfloor \frac{ka_j}{b_i} \rfloor)\)时，两者位置达到最优
\(\lfloor x \rfloor\)具有单调性，故可以提出到\(max\)函数外，并得到充分不必要条件\(max(\frac{k}{b_i},\frac{ka_i}{b_j})<=max(\frac{k}{b_j},\frac{ka_j}{b_i})\)
又因为\(\frac{ka_i}{b_j}>=\frac{k}{b_j},\frac{ka_j}{b_i}>=\frac{k}{b_i}\)，可以简化条件为\(a_ib_i<=a_jb_j\)。利用不等式传递性，可知i,j可以不相邻。
由以上条件对原二元关系组进行排序，得到的排列若相邻均用<连接则排列方式唯一，即无论输入时顺序，都会得到唯一答案；若其中用部分等号连接，则等号两端\(a_ib_i==a_jb_j\)，两两之间无具体顺序要求，均为最优。
(原题除了贪心，在计算答案时还需用高精度)

皇后游戏

洛谷P2123 皇后游戏

故技重施

用和国王游戏类似的方法，

这里我们先假设可以从邻项推广到不相邻两项(实际是不可以的)，如此可以得到一份能在洛谷ac的错误代码

#include <iostream>
#include <algorithm>

using namespace std;

const int N=20010;

struct Node
{
    int a,b;
    bool operator<(Node& y)
    {
        return min(a,y.b)<min(b,y.a);
    }
} dc[N];

long long ans,sum,t,n;

int main()
{
    cin>>t;
    while (t--)
    {
        cin>>n;
        for (int i=1;i<=n;++i)
        {
            cin>>dc[i].a>>dc[i].b;
        }
        sort(dc+1,dc+n+1);
        ans=sum=0;
        for (int i=1;i<=n;++i)
        {
            sum+=dc[i].a;
            ans=max(ans,sum)+dc[i].b;
        }
        cout<<ans<<endl;
    }
    return 0;
}

但这会被以下数据hack

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

输出为

16
17

输出两组输入的最终排序分别为

1 1
1 1
2 7
3 5

1 1
3 5
1 1
2 7

此时，排序后的排列方式不唯一，且两排列的最终答案不等价。
观察发现第二组数据23和34满足对相邻元素的比较，但是24两元素的比较结果是不符合“比较”的要求。
这是因为在这个式子，新定义的比较运算符不符合严格弱序，即满足了<的传递性（这个稍后再证明），但不满足=的传递性。使得等号在234的传递中出现了错误。

严格弱序

定义：对一个比较运算符<<(若不满足运算符则为!<<)，若其为严格弱序，则要求有以下性质：
1.x << x（非自反性）
2.若x << y,则y !<< x（非对称性）
3.若x << y, y << z,则x << z（传递性）
4.若x!<<y,y!<<z,z!<<y,y!<<z,则x!<<z,z!<<x（不可比性的传递性）
[如果觉得“不具有不可比性的传递性”不好理解的话，有个简单的例子：P(x,y)=x+1<y。这个偏序关系满足非自反性（x+1>x）、非对称性（x+1<y⇒y+1>x）和传递性（x+2<y+1<z），但不具有不可比性的传递性（1+1=2，2+1=3，1+1<3）]

满足严格弱序，则满足<=符号的传递性，即等号连接的元素两两换序而结果不变。
这非常重要，就像引言里提到的那样：如果最后的多种排列中存在不等价情况，就会导致答案错误。

皇后游戏后续

完善解法

问题在于\(min(a_i,b_j)=min(a_j,b_i)\)的时候。因为\(a_n\)的前缀和对答案有负影响，若此时将\(a_i\)较小的元素放在前面则可以解决问题。
[其实大多不能不满足严格弱序的排序，都可以通过进一步分类讨论的方式来消除等号带来的乱序]

#include <iostream>
#include <algorithm>

using namespace std;

const int N=20010;

struct Node
{
    int a,b;
    bool operator<(Node& y)
    {
        return min(a,y.b)==min(b,y.a)?a<y.a:min(a,y.b)<min(b,y.a);
    }
} dc[N];

long long ans,sum,t,n;

int main()
{
    cin>>t;
    while (t--)
    {
        cin>>n;
        for (int i=1;i<=n;++i)
        {
            cin>>dc[i].a>>dc[i].b;
        }
        sort(dc+1,dc+n+1);
        ans=sum=0;
        for (int i=1;i<=n;++i)
        {
            sum+=dc[i].a;
            ans=max(ans,sum)+dc[i].b;
        }
        cout<<ans<<endl;
    }
    return 0;
}

引文的末尾还有一个基于小数据的排序检测器，感兴趣的可以跳转阅读。

生产加工调度

洛谷P1248
这题是有贪心结论johnson准则的，可以利用文章中提供的结论证明两台机器时，johnson准则的正确性。
思路看第一篇题解即可。

这篇关于邻项交换排序类贪心的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！