题解：P11100 [ROI 2022 Day 2] 交换

· · 题解

最简题意

给定正整数 n 和 k，其中 n 可能含有前导零。你可以交换 n 中两个相邻的数码任意次，假设交换了 x 次，且最终得到的数为 n_1，你需要最大化 n_1−xk，并在此基础上最大化 n_1。

题意分析

虽然看似这个 n 很大，但是他就是很大，所以我们可以转战到 k 上面。这太小了，以至于仅仅只有十六位。不难发现，只要我们安排大于 k 之外的数，是不被 k 影响的，而且他只是求最终答案，与次数没关系。所以经粗略估计，我们可以将 n 分为两段。前一段直接用排序，因为它的取值与 k 无关。而后一段直接用贪心枚举次数，只要能换就换。而后一段大约在二十左右，但本篇题解用了二十六。具体可以参考代码及注释

更严谨的证明

当一次交换获得的收益超过 k 时我们一定会交换。一个数从个位交换到第 m 位至少需要交换 m-1 次，因此第 m 位从前 m-1 位找一个最大的数，至多需要代价 (x-1)k，而替换一个更大的数，权值至少增加 10^{x-1}，注意到当 x\geq20 时，10^{x-1}\geq(x-1)k 成立。

CODE

#include<bits/stdc++.h>
#define wk(x) write(x),putchar(' ')
#define wh(x) write(x),putchar('\n')
#define int __int128
#define ull unsigned long long
#define ri register int
#define INF 2147483647
#define mod 998244353
#define N 200005
#define NO printf("No\n")
#define YES printf("Yes\n")

using namespace std;
int n,m,k,jk,ans,sum,num,cnt,tot;char a[N],b[N];
int head[N],dis[N],wis[N],f[N],A[N],B[N],kis[N];

void read(int &x)
{
    x=0;int ff=1;char ty;
    ty=getchar();
    while(!(ty>='0'&&ty<='9'))
    {
        if(ty=='-') ff=-1;
        ty=getchar();
    }
    while(ty>='0'&&ty<='9')
        x=(x<<3)+(x<<1)+ty-'0',ty=getchar();
    x*=ff;return;
}

void write(int x){
    if(x==0){
        putchar('0');
        return;
    }
    if(x<0){
        x=-x;
        putchar('-');
    }
    char asd[201];int ip=0;
    while(x) asd[++ip]=x%10+'0',x/=10;
    for(int i=ip;i>=1;i--) putchar(asd[i]);
    return;
}

struct P{
    int x,id;
}vis[N];

bool cmp(P a,P b){
    return a.x>b.x||(a.x==b.x&&a.id<b.id);
}

bool cmp1(P a,P b){
    return a.id<b.id;
}

signed main()
{
    scanf("%s",a+1);read(m);n=strlen(a+1);int pl=max(n-26,(int)1);
    for(int i=1;i<=n;i++) dis[i]=a[i]-'0',vis[i].x=dis[i],vis[i].id=i;//输入。
    if(n>26){//多余26位才考虑两段。
        sort(1+vis,1+vis+n,cmp);//先全部排一遍序。
        sort(1+n-26+vis,1+vis+n,cmp1);//后半段按编号排回去，用贪心处理。
    }//记录
    for(int i=1;i<=n;i++) dis[i]=vis[i].x;
    for(int i=1;i<=n;i++) head[i]=dis[i];
    for(int G=0;G<=26*26+100;G++)//枚举后一段需要修改多少次。
    {
        int G1=G;
        __int128 p=0;//要开大一点。
        for(int i=pl;i<=n;i++) dis[i]=head[i];//初始化。
        for(int i=pl;i<=n;i++)
        {
            cnt=0;//一样初始化。
            for(int j=i;j<=n;j++)
                if(dis[j]>dis[cnt]&&G1>=j-i) cnt=j;//后面的比前面的大并且剩下的次数还够就记录。
            if(cnt) G1-=(cnt-i);//如果存在就更新。
            for(int j=cnt;j>i;j--) swap(dis[j],dis[j-1]);//更新答案。
        }
        for(int i=pl;i<=n;i++) p=p*10+dis[i];
        if((p-G*m>ans)||(p-G*m==ans&&p>k)){//判断是否满足条件。
            k=p;ans=p-G*m;//更新答案。
            for(int i=pl;i<=n;i++) kis[i]=dis[i];//同理。
        }
    }
    for(int i=1;i<pl;i++) write(dis[i]);//前面因为无论怎么换都有贡献，所以与答案没太大关联，另外输出。
    for(int i=pl;i<=n;i++) write(kis[i]);//后面的部分。
    return 0;
}