邻接交换和反悔贪心

基础

贪心算法 是一种在每一步决策时都采取当前状态下的最优选择，并通过一系列局部最优解来推导全局最优解的算法范式。

适用条件

局限性

贪心算法并不总是有效。当问题具有以下特征时，贪心策略通常会失效：

反悔贪心

反悔贪心先不管数据是否最优，先加入，后遇到更优数据则替换最劣数据（根据题意判断），通常需要用 优先队列（堆） 存储数据。

例题：P4053 建筑抢修

贪心目标

尽量多抢修建筑。

分析

显然，要抢修尽量多的建筑，需要优先修修理时间短、报废时间少的，晚修修理时间长、报废时间晚的。

使用反悔贪心思想，按报废时间从小到大排序，取消修理时间长的。

遍历时修理建筑

i

i

i，将修理时间加入大根堆。如果修理（结束）时间晚于建筑（

i

i

i）报废时间，则从大根堆取堆顶（时间最长的），取出后代表其取消修理。这样子保证了修理建筑数量相同，操作后的修理时间一定

<

=

<=

<=操作钱的修理时间。

#include<bits/stdc++.h>
using namespace std;
#define t1 second
#define t2 first
#define int long long
const int N = 150010;
priority_queue<int> q;
int n,ans,tot;
pair<int,int> p[N];
//tot已过时间，ans已修理建筑数量
signed main(){
scanf("%lld",&n);
for(int i = 1;i<=n;i++) scanf("%lld%lld",&p[i].t1,&p[i].t2);//注意t2对应first，按t2从小到大排序
sort(p+1,p+n+1);
for(int i = 1;i<=n;i++){
tot+=p[i].t1;
q.push(p[i].t1);
ans++;
if(tot>p[i].t2){
ans—;
tot-= q.top();
q.pop();
}
}
printf("%lld",ans);
return 0;
}

邻接交换

这通常解决需要一个最优排列顺序的问题

例题1：P1080 国王游戏

贪心目标

安排一个排队顺序，使获得奖赏最大的大臣所获得的奖赏尽量小。

分析

在排序中计算

i

i

i,

j

j

j 排列先后顺序。

令

s

s

s 为排在该大臣前面的所有人的左手上的数的乘积（不包括该大臣）。

设

c

i

c_i

ci​ 为大臣

i

i

i 所获得的奖赏。

a

i

a_i

ai​,

b

i

b_i

bi​ 分别为编号为

i

i

i 的大臣的左右手上的数。

当

i

i

i 前

j

j

j 后时

c

i

1

=

⌊

s

b

i

⌋

c_{i_1} = \\left\\lfloor \\frac{s}{b_i} \\right\\rfloor

ci1​​=⌊bi​s​⌋

c

j

1

=

⌊

s

×

a

i

b

j

⌋

c_{j_1} = \\left\\lfloor \\frac{s \\times a_i}{b_j} \\right\\rfloor

cj1​​=⌊bj​s×ai​​⌋

当

j

j

j 前

i

i

i 后时

c

j

2

=

⌊

s

b

j

⌋

c_{j_2} = \\left\\lfloor \\frac{s}{b_j} \\right\\rfloor

cj2​​=⌊bj​s​⌋

i

2

=

⌊

s

×

a

j

b

j

⌋

_{i_2} = \\left\\lfloor \\frac{s \\times a_j}{b_j} \\right\\rfloor

i2​​=⌊bj​s×aj​​⌋

由于需要奖赏最大的大臣的奖赏尽量小，顺序是否是

i

i

i 前

j

j

j 后由以下不等式是否成立决定

max

⁡

(

c

i

1

,

c

j

1

)

<

max

⁡

(

c

i

2

,

c

j

2

)

\\max(c_{i_1},c_{j_1}) < \\max(c_{i_2},c_{j_2})

max(ci1​​,cj1​​)<max(ci2​​,cj2​​)

max

⁡

(

⌊

s

b

i

⌋

,

⌊

s

×

a

i

b

j

⌋

)

<

max

⁡

(

⌊

s

×

a

j

b

i

⌋

,

⌊

s

b

j

⌋

)

\\max(\\left\\lfloor \\frac{s}{b_i} \\right\\rfloor,\\left\\lfloor \\frac{s \\times a_i}{b_j} \\right\\rfloor) < \\max(\\left\\lfloor \\frac{s \\times a_j}{b_i} \\right\\rfloor,\\left\\lfloor \\frac{s}{b_j} \\right\\rfloor)

max(⌊bi​s​⌋,⌊bj​s×ai​​⌋)<max(⌊bi​s×aj​​⌋,⌊bj​s​⌋) 约掉

s

s

s

max

⁡

(

⌊

1

b

i

⌋

,

⌊

a

i

b

j

⌋

)

<

max

⁡

(

⌊

a

j

b

i

⌋

,

⌊

1

b

j

⌋

)

\\max(\\left\\lfloor \\frac{1}{b_i} \\right\\rfloor,\\left\\lfloor \\frac{a_i}{b_j} \\right\\rfloor) < \\max(\\left\\lfloor \\frac{a_j}{b_i} \\right\\rfloor,\\left\\lfloor \\frac{1}{b_j} \\right\\rfloor)

max(⌊bi​1​⌋,⌊bj​ai​​⌋)<max(⌊bi​aj​​⌋,⌊bj​1​⌋) 同乘

b

i

×

b

j

b_i \\times b_j

bi​×bj​

max

⁡

(

b

j

,

a

i

×

b

i

)

<

max

⁡

(

a

j

×

b

j

,

b

i

)

\\max(b_j,a_i \\times b_i) < \\max(a_j \\times b_j,b_i)

max(bj​,ai​×bi​)<max(aj​×bj​,bi​) 显然，在

a

i

,

a

j

,

b

i

,

b

j

≥

1

a_i,a_j,b_i,b_j \\ge 1

ai​,aj​,bi​,bj​≥1 时，必然有

b

j

≤

a

j

×

b

j

b_j \\le a_j \\times b_j

bj​≤aj​×bj​

b

i

≤

a

i

]

×

b

i

b_i \\le a_i] \\times b_i

bi​≤ai​]×bi​ 则舍去

b

i

b_i

bi​,

b

j

b_j

bj​ 两项，原式得

a

i

×

b

i

<

a

j

×

b

j

a_i \\times b_i < a_j \\times b_j

ai​×bi​<aj​×bj​

得出当

a

i

×

b

j

<

a

j

×

b

j

a_i \\times b_j < a_j \\times b_j

ai​×bj​<aj​×bj​ 时，

i

i

i,

j

j

j 不交换

输入数据并排序，后用模拟法得出答案。但是题目涉及大数累乘，答案最大可达

10

4000

10^{4000}

104000 。即便是 __int128 类型也远远无法处理，因此需要高精度。示例代码为

60

p

t

s

60pts

60pts，无高精度处理。

60分代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1010;
int n,s,ans,t;
struct node{
int a,b;
}q[N];
bool cmp(node a,node b){
return a.a*a.b<b.a*b.b;
}
signed main(){
scanf("%lld%lld%lld",&n,&s,&t);
for(int i = 1;i<=n;i++){
scanf("%lld%lld",&q[i].a,&q[i].b);
}
sort(q+1,q+n+1,cmp);
for(int i = 1;i<=n;i++){
ans = max(s/q[i].b,ans);
s *= q[i].a;
}
printf("%lld",ans);
return 0;
}

例题2：P2123 皇后游戏

题外话，皇后游戏是邻接交换贪心的巅峰之作，还是非常吃脑子的。

贪心目标

安排一个排队顺序，使获得奖金最大的大臣所获得的奖赏尽量小。

分析

设

c

i

c_i

ci​ 为

i

i

i 大臣获得的奖金。

设

s

i

s_i

si​ 为

∑

k

=

1

n

a

j

\\sum_{k = 1}^n a_j

∑k=1n​aj​

a

i

a_i

ai​,

b

i

b_i

bi​ 分别为编号为

i

i

i 的大臣的左右手上的数。

由题得知

c

i

=

max

⁡

(

c

i

−

1

,

s

i

−

1

+

a

i

)

+

b

i

c_i = \\max(c_{i-1},s_{i-1} + a_i) + b_i

ci​=max(ci−1​,si−1​+ai​)+bi​

s

i

=

s

i

−

1

+

a

i

s_i = s_{i-1}+a_i

si​=si−1​+ai​

i

i

i 前

j

j

j 后

c

i

1

=

max

⁡

(

c

i

−

1

,

s

i

−

1

+

a

i

)

+

b

i

c_{i_1} = \\max(c_{i-1},s_{i-1}+a_i)+b_i

ci1​​=max(ci−1​,si−1​+ai​)+bi​

c

j

1

=

max

⁡

(

max

⁡

(

c

i

−

1

,

s

i

−

1

+

a

i

)

+

b

i

,

s

i

−

1

+

a

i

+

a

j

)

+

b

j

c_{j_1} = \\max(\\max(c_{i-1},s_{i-1}+a_i)+b_i,s_{i-1}+a_i+a_j)+b_j

cj1​​=max(max(ci−1​,si−1​+ai​)+bi​,si−1​+ai​+aj​)+bj​ 令

c

i

1

c_{i_1}

ci1​​ 和

c

j

1

c_{j_1}

cj1​​ 最大值

k

1

=

max

⁡

{

c

i

−

1

+

b

i

,

s

i

−

1

+

a

i

+

b

i

+

b

j

,

c

i

−

1

+

b

i

+

b

j

,

s

i

−

1

+

a

i

+

a

j

+

b

j

}

k_1 = \\max\\{ c_{i-1}+b_i, s_{i-1}+a_i+b_i+b_j, c_{i-1}+b_i+b_j, s_{i-1}+a_i+a_j+b_j \\}

k1​=max{ci−1​+bi​,si−1​+ai​+bi​+bj​,ci−1​+bi​+bj​,si−1​+ai​+aj​+bj​} 由以上皆为正整数，

c

i

−

1

+

b

i

<

c

i

−

1

+

b

i

+

b

j

c_{i-1}+b_i < c_{i-1}+b_i+b_j

ci−1​+bi​<ci−1​+bi​+bj​

k

1

=

max

⁡

{

s

i

−

1

+

a

i

+

b

i

+

b

j

,

c

i

−

1

+

b

i

+

b

j

,

s

i

−

1

+

a

i

+

a

j

+

b

j

}

k_1 = \\max\\{ s_{i-1}+a_i+b_i+b_j, c_{i-1}+b_i+b_j, s_{i-1}+a_i+a_j+b_j \\}

k1​=max{si−1​+ai​+bi​+bj​,ci−1​+bi​+bj​,si−1​+ai​+aj​+bj​}

j

j

j 前

i

i

i 后

c

j

1

=

max

⁡

(

c

j

−

1

,

s

j

−

1

+

a

j

)

+

b

j

c_{j_1} = \\max(c_{j-1},s_{j-1}+a_j)+b_j

cj1​​=max(cj−1​,sj−1​+aj​)+bj​

c

i

1

=

max

⁡

(

max

⁡

(

c

j

−

1

,

s

j

−

1

+

a

j

)

+

b

j

,

s

j

−

1

+

a

j

+

a

i

)

+

b

i

c_{i_1} = \\max(\\max(c_{j-1},s_{j-1}+a_j)+b_j,s_{j-1}+a_j+a_i)+b_i

ci1​​=max(max(cj−1​,sj−1​+aj​)+bj​,sj−1​+aj​+ai​)+bi​

令

c

i

2

c_{i_2}

ci2​​ 和

c

j

2

c_{j_2}

cj2​​ 最大值

k

2

=

max

⁡

{

c

j

−

1

+

b

j

,

s

j

−

1

+

a

j

+

b

j

+

b

i

,

c

j

−

1

+

b

j

+

b

i

,

s

j

−

1

+

a

j

+

a

i

+

b

i

}

k_2 = \\max\\{ c_{j-1}+b_j, s_{j-1}+a_j+b_j+b_i, c_{j-1}+b_j+b_i, s_{j-1}+a_j+a_i+b_i \\}

k2​=max{cj−1​+bj​,sj−1​+aj​+bj​+bi​,cj−1​+bj​+bi​,sj−1​+aj​+ai​+bi​} 由以上皆为正整数，

c

j

−

1

+

b

j

<

c

j

−

1

+

b

j

+

b

i

c_{j-1}+b_j < c_{j-1}+b_j+b_i

cj−1​+bj​<cj−1​+bj​+bi​

k

2

=

max

⁡

{

s

j

−

1

+

a

j

+

b

j

+

b

i

,

c

j

−

1

+

b

j

+

b

i

,

s

j

−

1

+

a

j

+

a

i

+

b

i

}

k_2 = \\max\\{ s_{j-1}+a_j+b_j+b_i, c_{j-1}+b_j+b_i, s_{j-1}+a_j+a_i+b_i \\}

k2​=max{sj−1​+aj​+bj​+bi​,cj−1​+bj​+bi​,sj−1​+aj​+ai​+bi​} 联

k

1

<

k

2

k_1<k_2

k1​<k2​

max

⁡

{

s

i

−

1

+

a

i

+

b

i

+

b

j

,

c

i

−

1

+

b

i

+

b

j

,

s

i

−

1

+

a

i

+

a

j

+

b

j

}

<

max

⁡

{

s

j

−

1

+

a

j

+

b

j

+

b

i

,

c

j

−

1

+

b

j

+

b

i

,

s

j

−

1

+

a

j

+

a

i

+

b

i

}

\\max\\{ s_{i-1}+a_i+b_i+b_j, c_{i-1}+b_i+b_j, s_{i-1}+a_i+a_j+b_j \\} < \\max\\{ s_{j-1}+a_j+b_j+b_i, c_{j-1}+b_j+b_i, s_{j-1}+a_j+a_i+b_i \\}

max{si−1​+ai​+bi​+bj​,ci−1​+bi​+bj​,si−1​+ai​+aj​+bj​}<max{sj−1​+aj​+bj​+bi​,cj−1​+bj​+bi​,sj−1​+aj​+ai​+bi​} 消去公共项

c

i

−

1

+

b

i

+

b

j

c_{i-1}+b_i+b_j

ci−1​+bi​+bj​

max

⁡

{

s

i

−

1

+

a

i

+

b

i

+

b

j

,

s

i

−

1

+

a

i

+

a

j

+

b

j

}

<

max

⁡

{

s

j

−

1

+

a

j

+

b

j

+

b

i

,

s

j

−

1

+

a

j

+

a

i

+

b

i

}

\\max\\{ s_{i-1}+a_i+b_i+b_j, s_{i-1}+a_i+a_j+b_j \\} < \\max\\{ s_{j-1}+a_j+b_j+b_i, s_{j-1}+a_j+a_i+b_i \\}

max{si−1​+ai​+bi​+bj​,si−1​+ai​+aj​+bj​}<max{sj−1​+aj​+bj​+bi​,sj−1​+aj​+ai​+bi​} 提取

s

i

−

1

s_{i-1}

si−1​ 和

s

j

−

1

s_{j-1}

sj−1​，从逻辑上我们知道

s

i

−

1

s_{i-1}

si−1​ 和

s

j

−

1

s_{j-1}

sj−1​ 意义一样，消去

max

⁡

{

a

i

+

b

i

+

b

j

,

a

i

+

a

j

+

b

j

}

<

max

⁡

{

a

j

+

b

j

+

b

i

,

a

j

+

a

i

+

b

i

}

\\max\\{ a_i+b_i+b_j, a_i+a_j+b_j \\} < \\max\\{ a_j+b_j+b_i, a_j+a_i+b_i \\}

max{ai​+bi​+bj​,ai​+aj​+bj​}<max{aj​+bj​+bi​,aj​+ai​+bi​} 分别提

a

i

+

b

j

a_i+b_j

ai​+bj​ 和

a

j

+

b

i

a_j+b_i

aj​+bi​

max

⁡

{

b

i

,

a

j

}

+

a

i

+

b

j

<

max

⁡

{

b

j

,

a

i

}

+

a

j

+

b

i

\\max\\{b_i,a_j\\}+a_i+b_j < \\max\\{b_j,a_i\\}+a_j+b_i

max{bi​,aj​}+ai​+bj​<max{bj​,ai​}+aj​+bi​ 移项

max

⁡

{

b

i

,

a

j

}

−

a

j

−

b

i

<

max

⁡

{

b

j

,

a

i

}

−

a

i

−

b

j

\\max\\{b_i,a_j\\}-a_j-b_i < \\max\\{b_j,a_i\\}-a_i-b_j

max{bi​,aj​}−aj​−bi​<max{bj​,ai​}−ai​−bj​

−

min

⁡

(

b

i

,

a

j

)

<

−

min

⁡

(

b

j

,

a

i

)

-\\min(b_i,a_j) < -\\min(b_j,a_i)

−min(bi​,aj​)<−min(bj​,ai​)

min

⁡

(

b

i

,

a

j

)

>

min

⁡

(

b

j

,

a

i

)

\\min(b_i,a_j) > \\min(b_j,a_i)

min(bi​,aj​)>min(bj​,ai​) 由于含

min

⁡

\\min

min 是偏序，要转换为全序，所以要转换一下。

bool cmp(pe x,pe y){
int xt = (x.a<=x.b)?0:1,yt = (y.a<=y.b)?0:1;
if(xt!=yt) return xt<yt;
if(xt==0) return x.a<y.a;
else return x.b>y.b;
}

题外话

原本是要把剩下几个贪心都写了的，但是关电脑忘保存了，直接哭晕在厕所