[CSP-S模拟测试]:字符交换（贪心+模拟）

题目传送门（内部题136）

输入格式

　　输入文件第一行为两个正整数$n,k$，第二行为一个长度为$n$的小写字母字符串$s$。

输出格式

　　输出一个整数，为对字符串$s$进行至多$k$次交换相邻字符的操作后，字符串$s$可能达到的最大的$m$指标。

样例

样例输入：

6 3
abacba

样例输出：

数据范围与提示

　　对于$40\%$的数据，满足$n\leqslant 10$。
　　对于$70\%$的数据，满足$n\leqslant 200$。
　　对于$100\%$的数据，满足$1\leqslant n\leqslant 4,000,1\leqslant k\leqslant n^2$。

题解

如果最终连续，那么一定有至少一个字符不动。

于是可以枚举字符，然后将同种字符最小的挪向它即可，用小根堆维护就好了。

其实因为答案满足单调性，所以可以用二分优化。

时间复杂度：$\Theta(n^2)$。

期望得分：$100$分。

实际得分：$100$分。

代码时刻

#include<bits/stdc++.h>

using namespace std;

int N,K;

char ch[4001];

int a[4001];

vector<int> pos[30];

int ans;

int main()

{

	scanf("%d%d",&N,&K);

	scanf("%s",ch+1);

	for(int i=1;i<=N;i++)

	{

		a[i]=ch[i]-'a'+1;

		pos[a[i]].push_back(i);

	}

	for(int i=1;i<=26;i++)

	{

		for(int j=0;j<pos[i].size();j++)

		{

			int L=(j==0)?1:pos[i][j-1]+(pos[i][j]-pos[i][j-1]+1)/2;

			int R=(j==pos[i].size()-1)?N:pos[i][j+1]-(pos[i][j+1]-pos[i][j]+1)/2;

			for(int k=L;k<=R;k++)

			{

				int cnt=1;

				int sum=abs(pos[i][j]-k);

				if(sum>K)continue;

				priority_queue<int,vector<int>,greater<int> > q;

				for(int l=0;l<pos[i].size();l++)

				{

					if(l<j)q.push(k-pos[i][l]-j+l);

					if(l>j)q.push(pos[i][l]-k-l+j);

				}

				while(q.size()&&sum+q.top()<=K)

				{

					cnt++;

					sum+=q.top();

					q.pop();

				}

				ans=max(ans,cnt);

			}

		}

	}

	printf("%d",ans);

	return 0;

}

rp++

巴特西