自动搬运

查看原文

来自洛谷，原作者为

	Red_river Q.E.D. ■|去证明，去实现|如果你总是和别人一起做他们做的事，你又怎么能知道自己是谁呢？|人生天地之间，若白驹之过隙，忽然而已。

搬运于2025-08-24 23:04:14，当前版本为作者最后更新于2025-01-21 20:58:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

最简题意

给定正整数 $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;
}