密码

贪心 树状数组

题面

给定一字符串$S$，现可进行$M$次交换相邻字符的操作，询问操作完后可能的最小字典序的字符串。

• $60pts$ $len_S\leq3000$
• $100pts$ $len_S\leq10^5,M\leq(len_S-8)^2+2$

解析

$len_S\leq3000$

显然从前往后枚举字符，暴力把可能的最小字符移到当前位置即可。
最坏复杂度$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\n",a+1);

$len_S\leq10^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;
}