密码（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。

来源

20121005

solution

对于字典序，按位贪心最优

对于每一位，我们从a~z贪心

那么我们只需要解决：

1.对于当前，每个字母最早出现位置（vector）

2.把某个字母换到当前位置的代价（树状数组）

#include<cstdio>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<vector>

#define maxn 100005

using namespace std;

int n,top[26];

long long m,tree[maxn];

char s[maxn],ans[maxn];

vector<int>f[26];

void jia(int k,int v){

	for(int i=k;i<=n;i+=i&-i)tree[i]+=v;

}

long long ask(int i){

	long long sum=0;

	for(;i>0;i-=i&-i)sum+=tree[i];

	return sum;

}

int main(){

	cin>>m;

	scanf("%s",s+1);n=strlen(s+1);

    for(int i=1;i<=n;i++){

		f[s[i]-'a'].push_back(i);

		jia(i,i-1);jia(i+1,1-i);

	}

	for(int i=1;i<=n;i++){

		for(int j=0;j<26;j++){

			if(top[j]>=f[j].size())continue;

			int t=f[j][top[j]];

			long long cost=ask(t);

			if(cost<=m){

				m-=cost;

				jia(t+1,-1);

				top[j]++;

				ans[i]=j+'a';

				break;

			}

		}

	}

	for(int i=1;i<=n;i++)printf("%c",ans[i]);cout<<endl;

    return 0;

}

巴特西

密码（pasuwado）

密码（pasuwado）

题目描述

输入

输出

样例输入

样例输出

提示

来源

最新文章

热门文章

巴特西

密码 （pasuwado）

密码 （pasuwado）

题目描述

输入

输出

样例输入

样例输出

提示

来源

最新文章

热门文章

密码（pasuwado）

密码（pasuwado）