3 、 密码( ( pasuwado) )

【问题描述】

哪里有压迫，哪里就有反抗。
moreD 的宠物在法庭的帮助下终于反抗了。作为一只聪明的宠物，他打算把
魔法使 moreD 的魔法书盗去，夺取 moreD 的魔法能力。但 moreD 怎么会让自己的
魔法书轻易地被盗取？moreD 在魔法书上设置了一个密码锁，密码锁上有一个问
题。
施以斯卧铺魔法吧，你有 M 次机会，如此将得完美密码。
然后是一串小写字母串。
moreD 的宠物斯卧铺魔法就是施法时的字符串其中相邻两位交换。
而 moreD 对于完美密码的定义自然是最小字典序了。
请帮助 moreD 的宠物，想出密码吧。

【输入格式】

第一行一个整数 M，表示操作次数。
第二行一串小写字母组成的字符串 S，如题目所示。

【输出格式】

输出完美密码。

【输入样例】

3
dcba

【输出样例】

adcb

【数据范围】

对于 30%的数据|S|≤10
对于 60%的数据|S|≤3,000
对于 100%的数据 8≤|S|≤100,000，M≤(|S|-8)^2+2

【后记】

宠物最终战胜了 moreD,和自己的宠物快乐地生活着。

【样例解释】

先对第 3，4 两位施法，字符串变成 dcab，然后对第 2，3 两位施法，字符串
变成 dacb，最后对第 1，2 两位施法，字符串变成 adcb。

【算法一】

深度优先搜索：每次枚举交换的位置，时间复杂度 O(N^M)。期望得分 30%

【算法二】

对于此类问题可以使用贪心思想：由于题目要求字典序，可以贪心地从前到
后确定每一位的字母。字母肯定是从小到大地枚举，操作距离内的枚举字母的话
肯定会贪心地把这个字母换入目标位置。而选择枚举的字母就是贪心地选择尽量
前的字母。证明略。
时间复杂度为 O(N^2),空间复杂度为 O(N)。期望得分 60%

【算法三】

算法二可以进行优化。
算法主要耗时在寻找每个字母目前最前是哪一个，可以用链表维护。另外目
前需要的操作数可以就等于目标字母所在位置之前有多少个剩余的没有用的字
母，可以用树状数组维护。
时间复杂度为 O(NlogN),空间复杂度为 O(N)。期望得分 100%

参考代码 

#include<bits/stdc++.h>
using namespace std;
long long n,k,now;
int tot=1;
char a[100006];
int s[100005];
void add(int x,int ad)
{
	for(;x<tot;x+=x&-x)
		s[x]+=ad;
}
int ask(int x)
{
	int ans=0;
	for(;x;x-=x&-x)
		ans+=s[x];
	return ans;
}
deque< int > v[50];
int lxl;
char ans[500005];
int main()
{
	cin>>n;
	scanf("%s",a+1);
	for(;a[tot]>='a'&&a[tot]<='z';tot++)
		v[int(a[tot]-'a')].push_back(tot);
	now=1;
	while(now<tot)
	{
		for(int i=0;i<26;i++)
			if(v[i].size()&&v[i].front()+ask(v[i].front())-now<=n)
			{
				k=v[i].front()+ask(v[i].front());
				lxl=v[i].front();
				v[i].pop_front();
				break;
			}
		n-=(k-now);
		ans[now]=a[lxl];
		add(1,1);
		add(lxl,-1);	
		now++;
	}
	for(int i=1;i<now;i++)
		cout<<ans[i];
	return 0;
}