自动搬运

查看原文

来自洛谷，原作者为

	wzb13958817049 **

搬运于2025-08-24 22:21:48，当前版本为作者最后更新于2023-11-12 08:40:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

贪心，因为 Mirko 每次只会拿最后一个单词，所以 Slavko 要想赢就要拿剩下单词中字典序最小的且排在越后面越好。这样我们可以很好的想到暴力，去拿 $O(n)$ 的时间复杂度去跑一遍剩余序列找最小且最后的字母。但是只有 $40$ 分，因此就可以想到把所有字母的位置保存在数组中，从而去寻找最小且最后的字母。

#include<bits/stdc++.h>
using namespace std;
long long n,j;
string a,ans1,ans2;//ans1表示Slavko拿到的最美丽单词
//ans2表示Mirko拿到的单词
vector<long long> mp[27];
bool vis[200005];//该位置是否被访问过
int main(){
	cin>>n>>a;
	for(int i=0;i<a.size();i++) mp[a[i]-'a'+1].push_back(i);//把字母保存到vector中
	j=n-1;//最后一个字母的下标
	while(ans1.size()+ans2.size()<a.size()){
		while(vis[j]==1 && j!=0) j--;//Mirko先手
		ans2+=a[j];vis[j]=1;//记录下标为j的字母已经被拿走
		bool falg=0;
		for(int i=1;i<=26;i++){//从小到大遍历，找到第一个有的字母(最小)
			for(int k=mp[i].size()-1;k>=0;k--){//从后往前遍历因为越后面越好
				if(vis[mp[i][k]]==0){//如果没被拿走
					ans1+='a'+i-1;
					vis[mp[i][k]]=1;//标记
					mp[i].erase(mp[i].begin()+k);//删除
					falg=1;
					break;
				}
			}
			if(falg==1) break;
		}	
	}
	if(ans1<ans2) cout<<"DA";
	else cout<<"NE";
	cout<<"\n"<<ans1;//输出答案
	return 0;	
}

但是因为代码太朴素，还是会 $T$，那怎么办呢？剪枝，记录上一次拿的字母，下次从上一个字母开始访问，可以大大的省时间。

ACcode

#include<bits/stdc++.h>
using namespace std;
long long n,j,kkk;
string a,ans1,ans2;
vector<long long> mp[27];
bool vis[200005];
int main(){
	cin>>n>>a;
	for(int i=0;i<a.size();i++) mp[a[i]-'a'+1].push_back(i);
	j=n-1;
	while(ans1.size()+ans2.size()<a.size()){
		while(vis[j]==1 && j!=0) j--;
		ans2+=a[j];vis[j]=1;
		bool falg=0;
		for(int i=kkk;i<=26;i++){
			for(int k=mp[i].size()-1;k>=0;k--){
				if(vis[mp[i][k]]==0){
					ans1+='a'+i-1;
					vis[mp[i][k]]=1;
					mp[i].erase(mp[i].begin()+k);
					kkk=i;
					falg=1;
					break;
				}
			}
			if(falg==1) break;
		}	
	}
	if(ans1<ans2) cout<<"DA";
	else cout<<"NE";
	cout<<"\n"<<ans1;
	return 0;	
}