浅谈Exchange Argument贪心

FelFa_1414666 · 2022-04-07 17:33:58 · 个人记录

这周刷了几道有关的题目，小小的写一个对Exchange Argument思想的理解和总结，欢迎大佬来吊打我。

Exchange Argument（或许可以翻译为交换论证？）是一种贪心地构造最优序列的思想。通常这类题目会有sorting，greedy这类标签。

它适用于在一个操作序列中，找到最优的操作顺序。通常会通过定义一个权值比较器，对所有操作按一定标准排序来完成这一过程。

通常定义的权值比较器需要满足以下两个性质：

传递性，即 x<y\land y<z \Rightarrow x<z，这使得权值满足全序关系，可以排序。
交换性，即 x<y\Rightarrow y>x，这样保证排序结果唯一。

口胡完毕，来看一道典型题。

P1080 [NOIP2012提高组] 国王游戏

要求大臣们的最优顺序，考虑相邻的两个大臣 i、j，设它们之前所有人左手之积为 A，考虑交换它们两个，对前后并不会造成影响，只会对它们本身的取值有影响。列式可得，当 i 在 j 前更优，一定满足：

\max(\frac{A}{b_i},\frac{A\times a_i}{b_j})<\max(\frac{A}{b_j},\frac{A\times a_j}{b_i})

展开：

(\frac{1}{b_i}<\frac{1}{b_j}\land \frac{a_i}{b_j}<\frac{1}{b_j})\lor (\frac{1}{b_i}<\frac{a_j}{b_i}\land \frac{a_i}{b_j}<\frac{a_j}{b_i})

化简逻辑条件，剩下：

a_i\times b_i<a_j\times b_j

所以将所有大臣以 a\times b 为权值升序排序，然后模拟一下过程求出答案。（以下代码省略150行的高精模板）

int n;
struct Person//定义类
{
    ll l,r;
    bool operator<(Person &B)//权值比较器
    {
        return (l*r)<(B.l*B.r);
    }
}a[1005],k;
Int ans;
int main()
{
    scanf("%d%lld%lld",&n,&k.l,&k.r);
    for(int i=0;i<n;i++)
        scanf("%lld%lld",&a[i].l,&a[i].r);
    sort(a,a+n);//按权值升序排序
    Int pro=k.l;
    for(int i=0;i<n;i++)//模拟过程
    {
        Int q=pro/a[i].r;
        if (q>ans)
            ans=q;
        pro*=(Int)a[i].l;
    }
    printf("%lld", ans.s[ans.s[0]]);//输出高精度变量
    for(int i = ans.s[0] - 1; i >= 1; i--)
        printf("%09lld", ans.s[i]);
    putchar('\n');
    return 0;
}

时间复杂度: \operatorname O(n\log n)

空间复杂度: \operatorname O(n)

URAL1522.Factory

考虑顺序固定时，用 dp 求总时间。

\begin{cases}dpa_i=dpa_{i-1}+a_i\\dpb_i=\max(dpa_i,dpb_{i-1})+b_i\\dpc_i=\max(dpb_i,dpc_{i-1})+c_i\end{cases}

总时间为 dpc_{n-1}。

考虑只有相邻两个物品 i,j，根据 dp 式和题目条件得出式子，若 i 在前更优，则满足：

ai-ci+max(aj+bj,bi+ci)<aj-cj+max(ai+bi,bj+bj)

化简得出：所有 a<c 的物品在前，按 a+b 升序排序；a>=c 的物品在后，按 b+c 降序排序。排序后 dp 求时间。

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define F first
#define S second
using namespace std;
int n;
struct item//定义物品类
{
    int id;
    ll a,b,c;
    bool operator<(item &B)//权值比较器
    {
        if (a<c) return (B.a>=B.c||a+b<B.a+B.b);
        else return (B.a>=B.c&&b+c>B.b+B.c);
    }
}x[100005];
int main()
{
    ios::sync_with_stdio(false),cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        x[i].id=i;
        cin>>x[i].a>>x[i].b>>x[i].c;
    }
    sort(x+1,x+n+1);//按权值排序
    ll dpa=0ll,dpb=0ll,dpc=0ll;//dp求时间
    for(int i=1;i<=n;i++)
    {
        dpa+=x[i].a;
        dpb=max(dpa,dpb)+x[i].b;
        dpc=max(dpb,dpc)+x[i].c;
    }
    cout<<dpc<<endl;
    for(int i=1;i<=n;i++)
        cout<<x[i].id<<" ";
    cout<<endl;
    return 0;
}

时间复杂度: \operatorname O(n\log n)

空间复杂度: \operatorname O(n)

实际上，在很多问题中，不要求将序列中所有操作全部做一遍，而是按一定顺序选取操作的一个子集，使其最优。对于这种问题，同样地，我们先将所有操作按一个贪心的权值比较器排序。那么，接下来选的操作序列，一定是排序过后序列的一个子序列。问题就转化为 01 背包问题解决。

CF277D. Google Code Jam

不难想到，如果我们确定了要做的题目有哪些，那么期望分数是确定的。先做完所有 small，再做所有 large，一定能保证期望时间最小。且 small 的顺序对期望时间毫无影响。只需要考虑对所有 large 排序。

考虑交换相邻的两个 large i 和 j，先做 i 的期望时间：(1-p_j)(t_i+t_j)+(1-p_i)p_jt_i，先做 j 的期望时间：(1-p_i)(t_i+t_j)+(1-p_j)p_it_j，所以若先做 i 更优，则满足：

(1-p_j)(t_i+t_j)+(1-p_i)p_jt_i<(1-p_i)(t_i+t_j)+(1-p_j)p_it_j

化简：

\dfrac{t_i(1-p_i)}{p_i}<\dfrac{t_j(1-p_j)}{p_j}

以此为 large 的权值对所有问题升序排序。注意公式中除数不能为 0 。然后跑一遍带期望的 01 背包 dp 。~~（什么恶心题目）~~

考虑当前题目不做、做 small、做small 和 large 三种情况分别转移。注意本题精度要求较高，要开 long double。

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define pii pair<int,int>
#define pdd pair<ld,ld>
#define mp make_pair
#define F first
#define S second
#define eps 1e-9
using namespace std;
int n,T;
pdd dp[1005][1565];
void chmax(pdd &a,pdd b)//更新dp值
{
    if (b.F-a.F>eps||(b.F-a.F>-eps&&a.S-b.S>eps))//不写eps会被卡WA34，别问我怎么知道的
        a=b;
}
struct task//问题类
{
    ld a1,a2,t1,t2,p;
    bool operator<(task &B)//权值比较器
    {
        return 1.0*t2*p*(1.0-B.p)<1.0*B.t2*B.p*(1.0-p);
    }
}a[1005];
int main()
{
    ios::sync_with_stdio(false),cin.tie(nullptr);
    cout<<fixed<<setprecision(12);
    cin>>n>>T;
    for(int i=0;i<n;i++)
        cin>>a[i].a1>>a[i].a2>>a[i].t1>>a[i].t2>>a[i].p;
    sort(a,a+n);//按权值升序排序
    for(int i=0;i<=n;i++)
        for(int j=0;j<=T;j++)
            dp[i][j]=mp(-1.0,-1.0);
    dp[0][0]=mp(0.0,0.0);
    for(int i=0;i<n;i++)//01背包
        for(int j=0;j<=T;j++)
            if (dp[i][j].F!=-1.0)
            {
                ld x=dp[i][j].F,y=dp[i][j].S;
                chmax(dp[i+1][j],dp[i][j]);
                if (j+(int)a[i].t1<=T)
                    chmax(dp[i+1][j+(int)a[i].t1],mp(x+a[i].a1,y+a[i].t1));
                if (j+(int)a[i].t1+(int)a[i].t2<=T)
                    chmax(dp[i+1][j+(int)a[i].t1+(int)a[i].t2],
                    mp(x+a[i].a1+(1.0-a[i].p)*a[i].a2,a[i].t1+(1.0-a[i].p)*(1.0*j+a[i].t2)+a[i].p*y));
            }
    pdd ans=mp(-1.0,-1.0);
    for(int j=0;j<=T;j++)
        chmax(ans,dp[n][j]);
    cout<<ans.F<<" "<<ans.S<<endl;
    return 0;
}

时间复杂度: \operatorname O(n\log n+nT)

空间复杂度: \operatorname O(nT)

Hitachi2020D Manga Market

这题具体题解见我的另一篇博客

同样的套路，先对所有商店进行排序，使得最优序列一定是满足此顺序的。考虑交换相邻两个商店 i 和 j ，假设在此之前已经花费了 t 的时间。

所以：若先去 i 更优，则满足：

(a_i+a_j)t+a_ia_jt+a_j(b_i+1)+b_i+b_j+2<(a_i+a_j)t+a_ia_jt+a_i(b_j+1)+b_i+b_j+2

化简得：

\dfrac{b_i+1}{a_i}<\dfrac{b_j+1}{a_j}

这个比较满足全序关系，所以将所有商店按 \dfrac{b+1}{a} 升序排序，如果 a=0 定义其权值为 +\infty+b。

接下来是 01 背包 dp。

常规的 01 背包转移，考虑当前商店去或不去：

dp_{i,j}=\min(dp_{i-1,j},dp_{i-1,j-1}+a_i\times(dp_{i-1,j-1}+1)+b_i)

这样做的时间复杂度是 O(n^2\times 1)=O(n^2) 的，我们要对状态进行优化。

手算几组数据会发现，对于 a>0 的商店，每去一次，当前时间至少翻 a 倍。这提示我们实际上能去的最大商店数是很少的。先忽略 a=0 的所有商店，剩下商店即使全部 a=1，最终能去的最大商店数仍不超过 \lg T 。所以 dp 状态数优化到了 O(n\log T)。最后对每个 dp_{n,j}，再对剩下的所有 a=0 的商店跑一遍贪心即可。

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define F first
#define S second
using namespace std;
const int INF=1000000000000000007;
int n,T,pos,ans;
struct store//定义商店类
{
    int x,y;
    bool operator<(store &B)//权值比较器
    {
        if (x==0&&B.x==0)
            return y<B.y;
        return (y+1)*B.x<(B.y+1)*x;
    }
}a[200005];
int dp[200005][35];//n*lgT的dp数组
signed main()
{
    ios::sync_with_stdio(false),cin.tie(nullptr);
    cin>>n>>T;
    for(int i=0;i<n;i++)
        cin>>a[i].x>>a[i].y;
    sort(a,a+n);//按权值升序排序
    while(pos<n&&a[pos].x>0)
        pos++;//找到第一个a=0的商店下标
    for(int i=0;i<=pos;i++)
        fill(dp[i],dp[i]+30,INF);
    dp[0][0]=0ll;
    for(int i=0;i<pos;i++)
        for(int j=0;j<30;j++)if (dp[i][j]<=T)//01背包dp
        {
            dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
            dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+1+a[i].x*(dp[i][j]+1)+a[i].y);
        }
    for(int j=0;j<30;j++)if (dp[pos][j]<=T)
    {//对剩下所有a=0的商店再剩余时间内跑一遍贪心
        int i=pos,t=dp[pos][j],cur=j;
        while(i<n&&t+1+a[i].y<=T)
        {
            t+=1+a[i].y;
            cur++;
            i++;
        }
        ans=max(ans,cur);//记录最大答案
    }
    cout<<ans<<endl;
    return 0;
}

时间复杂度：O(n\log n+n\log T)
空间复杂度：O(n\log T)

以上都是一些常规的利用 Exchange Argument 构造贪心算法的题目。还有一类题目中，除了最优序列的要求，还给出一个树形结构，要求操作序列满足树上的拓扑序，即节点必须在所有祖先之后。这类问题我们就暂且叫做 树上的Exchange Argument 。这类题目也是有套路可循的，下面来看 3 道典型题。

POJ2054.Color a Tree

首先我们考虑没有树上拓扑序的限制，那么最优解一定是将所有节点按权值降序排序。我们希望答案序列尽可能接近这个序列，那么想到一个贪心：

对于权值最大的节点，一旦其父亲被选，就立即选它。

可以证明这样做一定不会使答案更劣。既然这个节点和父亲先后被选，那么可以视为将它们合并为一个节点。

接下来的问题是：如何处理合并后节点的权值？考虑合并的两个节点权值 a,b，令有一个可选节点权值为 c ，分别考虑顺序 a,b,c 和 c,a,b 的差异，若 a,b,c 更优，一定满足：

a+2b+3c<c+2a+3b$，即 $c<\frac{a+b}{2}

2 个以上节点的合并，同理可以推式子。得出合并的节点权值为其中所有节点的平均值。

维护并查集，每个并查集记录节点个数、总和、最后一个涂的元素。一开始每个点独立成集放在优先队列中，每次弹出平均值最大的集与父亲集合并。同时对每个小节点维护单向指针，表示涂完这个的下一个，在合并时维护和改动。最后所有集合并为1个，按照根一直顺链表向后遍历求最小总代价。

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <functional>
#include <utility>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define F first
#define S second
using namespace std;
int n,rt,aa[1005],a[1005],fa[1005],sz[1005],p[1005],r[1005],tl[1005];
//aa原节点权值，a每个合并集权值之和，fa所属并查集，sz集中节点个数，p父亲节点，r链表，tl集中最后一个涂的节点
bool vis[1005];
int find(int x){return fa[x]=(fa[x]==x?x:find(fa[x]));}
void merge(int x,int y)//并查集合并
{
    x=find(x),y=find(y);
    r[tl[y]]=x;//修改指针
    tl[y]=tl[x];
    sz[y]+=sz[x];
    a[y]+=a[x];
    fa[x]=y;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    while(cin>>n>>rt,n)
    {
        --rt;
        p[rt]=-1;
        for(int i=0;i<n;i++)
            fa[i]=tl[i]=i;
        memset(vis,0,sizeof(vis));
        memset(r,-1,sizeof(r));
        fill(sz,sz+n,1);
        for(int i=0;i<n;i++)
        {
            cin>>a[i];
            aa[i]=a[i];
        }
        for(int i=0;i<n-1;i++)
        {
            int u,v;
            cin>>u>>v;--u,--v;
            p[v]=u;
        }
        priority_queue<pair<double,int> > pq;
        for(int i=0;i<n;i++)
            pq.push(mp(1.0*a[i],i));
        while(!pq.empty())
        {
            int u=pq.top().S;
            pq.pop();
            if (vis[u])
                continue;
            vis[u]=1;
            if (p[u]!=-1)
            {//与父亲所在集合合并
                merge(u,p[u]);
                int x=find(p[u]);
                pq.push(mp(1.0*a[x]/(1.0*sz[x]),x));//将合并后新节点压入优先队列
            }
        }
        int k=1,cur=rt,ans=0;
        do//按顺序模拟求一边答案
        {
            ans+=k*aa[cur];
            k++;
            cur=r[cur];
        }while(cur!=-1);
        cout<<ans<<endl;
    }
    return 0;
}

时间复杂度: \operatorname O(n\log n)

空间复杂度: \operatorname O(n)

AGC023F - 01 on Tree

本题在另一篇博客有详细题解。

与上一题同样的套路，权值贪心+并查集合并节点+优先队列。~~（AGC的F这么版的吗~~

设两个节点（单个节点或多个合并的节点）分别为 a 和 b，设 a 节点包含的所有小节点中有 a_0 个 0 和 a_1 个 1。同样地，b 包含的所有小节点中有 b_0 个 0 和 b_1 个 1。分别考虑先选 a 与先选 b 造成的逆序对个数谁更优，当且仅当：a_1\times b_0<b_1\times a_0 时，先选 a 更优。即：

\dfrac{a_1}{a_0}<\dfrac{b_1}{b_0}

所以新合并节点的权值就是 \dfrac{cnt_1}{cnt_0}。（注意 cnt_0=1 时权值赋为 +\infty）

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pdi pair<double,int>
#define mp make_pair
#define F first
#define S second
using namespace std;
const double INF=1e18;
int n,a[200005],fa[200005],p[200005];
bool vis[200005];
ll ans,cnt1[200005],cnt0[200005];
int find(int x){return (fa[x]==x?x:find(fa[x]));}
void merge(int x,int y)//并查集合并操作
{
    x=find(x),y=find(y);
    ans+=cnt1[y]*cnt0[x];//记录对逆序对总数的贡献
    cnt1[y]+=cnt1[x];//合并后加上0 1个数
    cnt0[y]+=cnt0[x];
    fa[x]=y;
}
int main()
{
    ios::sync_with_stdio(false),cin.tie(nullptr);
    cin>>n;
    p[0]=-1;
    for(int i=1;i<n;i++)
    {
        cin>>p[i];
        --p[i];
    }
    priority_queue<pdi,vector<pdi>,greater<pdi> > pq;//优先队列按权值升序存节点
    for(int i=0;i<n;i++)
    {
        fa[i]=i;
        cin>>a[i];
        if (a[i]) ++cnt1[i];
        else ++cnt0[i];
        pq.push(mp((cnt0[i]==0?INF:1.0*cnt1[i]/(1.0*cnt0[i])),i));
    }
    while(!pq.empty())
    {
        int u=pq.top().S;
        pq.pop();
        if (vis[u])
            continue;
        vis[u]=1;
        if (p[u]!=-1)//与父亲所在节点合并
        {
            int x=find(p[u]);
            merge(u,x);
            pq.push(mp((cnt0[x]==0?INF:1.0*cnt1[x]/(1.0*cnt0[x])),x));//将新节点加入优先队列
        }
    }
    cout<<ans<<endl;
    return 0;

HDU6326.Munster Hunter

依然用树上 Exchange Argument 的套路考虑。但是这里合并节点的信息并不是题目自带的，需要稍加分析。

求起始的最小血量，其实使过程中血量最低值尽可能大，这样起始时加上血量最低值的相反数就能保证血量永远不低于 0。

基于这一思想，对每个合并的节点集合维护 a 表示过程中最低值的相反数，b 表示过程中血量总共变化量+a，这样经过这一节点的过程可以视为先 -a ,再 +b 。根据同样地套路，列式分析可以得到一个排序策略：

先处理 a<b 的集合，再处理 a\ge b 的集合一定更优。a<b 的集合之间按 a 升序排序最优，a\ge b 的集合之间按 b 降序排序最优。

然后继续沿用并查集+优先队列的方式，将所有节点按权值优先级依次合并。同时对每个节点维护单向指针表示涂完这个的下一个。最后按链表指针遍历模拟过程，得到全过程中血量最小值 mn ，答案为\max(-mn,0)。

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <functional>
#include <utility>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <cstring>
#define ll long long
#define pb push_back
#define pli pair<ll,int>
#define mp make_pair
#define F first
#define S second
using namespace std;
const ll INF=100000000000000007;
int n,p[100005],fa[100005],tl[100005],r[100005];//p父亲，fa所属并查集，tl集中最后一个操作节点，r链表指针
ll aa[100005],bb[100005],a[100005],b[100005];
vector<int> G[100005];//邻接表
bool vis[200005];
int find(int x){return (fa[x]==x?x:find(fa[x]));}
void merge(int x,int y)//合并并查集
{
    x=find(x),y=find(y);
    ll sum=b[y]+b[x]-a[x]-a[y];
    a[y]=-min(-a[y],-a[y]+b[y]-a[x]);//计算新节点a、b值
    b[y]=sum+a[y];
    r[tl[y]]=x;//修改指针
    tl[y]=tl[x];
    fa[x]=y;
}
void dfs(int u,int par)//求每个节点父亲
{
    p[u]=par;
    for(auto to:G[u])
        if (to!=par)
            dfs(to,u);
}
void run()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        G[i].clear();
    for(int i=0;i<n;i++)
    {
        r[i]=-1;
        fa[i]=tl[i]=i;
        vis[i]=0;
    }
    a[0]=b[0]=0ll;
    for(int i=1;i<n;i++)
    {
        scanf("%lld%lld",&a[i],&b[i]);
        aa[i]=a[i],bb[i]=b[i];
    }
    for(int i=0;i<n-1;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);--u,--v;
        G[u].pb(v);
        G[v].pb(u); 
    }
    dfs(0,-1);
    priority_queue<pli,vector<pli>,greater<pli> > pq;
    for(int i=1;i<n;i++)
    {
        ll w=(a[i]<b[i]?a[i]:INF-b[i]);//定义权值，a<b在前以a升序排序，a>=b在后以b降序排序
        pq.push(mp(w,i));
    }
    while(!pq.empty())
    {
        ll ww=pq.top().F;
        int u=pq.top().S;
        pq.pop();
        ll w=(a[u]<b[u]?a[u]:INF-b[u]);
        if (vis[u]||ww!=w)//该节点操作过或已与其他节点合并
            continue;
        vis[u]=1;
        if (p[u]!=-1)
        {
            int x=find(p[u]);
            merge(u,x);//与父亲所在集合合并
            w=(a[x]<b[x]?a[x]:INF-b[x]);
            pq.push(mp(w,x));
        }
    }
    int u=r[0];
    ll ans=0ll,cur=0ll;
    do//根据链表遍历模拟全过程
    {
        cur-=aa[u];
        ans=min(ans,cur);
        cur+=bb[u];
        u=r[u];
    }while(u!=-1);
    printf("%lld\n",-ans);
}
signed main()
{
    int TT;
    scanf("%d",&TT);
    while(TT--)
        run();
    return 0;
}

时间复杂度: \operatorname O(n\log n)

空间复杂度: \operatorname O(n)

总结

此类题目围绕最优排序展开，关键点在于考虑贪心策略的方式：假设两个操作顺序交换是否会更优，总而得出每个操作的权值。然后再结合 01 背包或其他数据结构求该顺序下的最优解。

浅谈Exchange Argument贪心

P1080 [NOIP2012提高组] 国王游戏

URAL1522.Factory

CF277D. Google Code Jam

Hitachi2020D Manga Market

POJ2054.Color a Tree

AGC023F - 01 on Tree

HDU6326.Munster Hunter

总结