https://zybuluo.com/ysner/note/1176102
题面
给定一字符串(S)，现可进行(M)次交换相邻字符的操作，询问操作完后可能的最小字典序的字符串。
- (60pts) (len_Sleq3000)
- (100pts) (len_Sleq10^5,Mleq(len_S-8)^2+2)
解析
(len_Sleq3000)
显然从前往后枚举字符，暴力把可能的最小字符移到当前位置即可。
最坏复杂度(O(n^2)),期望(60pts)。
但复杂度不太满，如数据过水可获得(80-90pts)。
scanf("%lld",&n);
scanf("%s",a+1);len=strlen(a+1);
fp(i,1,len)
{
re ll s=min(i+n,len),pos=i;char zsy=a[i];
fp(j,i,s)
if(a[j]<zsy||(a[j]==zsy&&j<pos)) zsy=a[j],pos=j;
n-=(pos-i);
zsy=a[pos];fq(j,pos,i+1) a[j]=a[j-1];a[i]=zsy;
if(!n) break;
}
printf("%s
",a+1);
(len_Sleq10^5)
发现寻找可行域内最小字符很耗时间。
我们可以用树状数组维护每个字符前需要交换的字符数，用链表维护(26)个字符出现的第一个位置。
关键在于交换字符后，我们不关心字符间的顺序，只关心字符个数。
交换完后把本在后面的字符删掉即可。
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2e5;
ll n,len,h[N],nxt[N],t[N];
char a[N];
il void add(re ll x,re ll w){for(;x<=len;x+=x&-x) t[x]+=w;}
il ll Query(re ll x){re ll ans=0;for(;x;x-=x&-x) ans+=t[x];return ans;}
int main()
{
freopen("pasuwado.in","r",stdin);
freopen("pasuwado.out","w",stdout);
scanf("%lld",&n);
scanf("%s",a+1);len=strlen(a+1);
fq(i,len,1) nxt[i]=h[a[i]-96],h[a[i]-96]=i;//为26个字母按从前往后顺序分别建立位置链表，原先的h移到next
fp(i,1,len) add(i,1);
fp(i,1,len)
{
fp(j,1,26)
{
re int pos=h[j];
if(!pos) continue;
re int sum=Query(pos-1);
if(n>=sum)
{
n-=sum;
add(pos,-1);
h[j]=nxt[pos];//改变移完的字符的第一位
printf("%c",j+96);
break;
}
}
}
puts("");
fclose(stdin);
fclose(stdout);
return 0;
}