社区讨论

玄关,求大佬调

P1124文件压缩参与者 2已保存回复 4

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
4 条
当前快照
1 份
快照标识符
@m21lhy2d
此快照首次捕获于
2024/10/09 16:15
去年
此快照最后确认于
2025/11/04 17:35
4 个月前
查看原帖
题解里都是n方的复杂度,我写的O(n),感觉没问题,希望大佬能帮忙看看思路哪出错了。
CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int re(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
char s[100002],a[100002];
int main(){
	int n=re();
	cin>>s+1;
	int p=re();
	for(int i=1;i<=n;i++){
		a[i]=s[i];
	}
  
	sort(a+1,a+n+1);
	string ans=s[p];
  
	if(n==1){
		cout<<s[1];
		return 0;
	}
	if(n==2){
		cout<<ans+a[p];
		return 0;
	}
  
	stack<char>Ans,now[1000];
	int flag=0;
	for(int i=1;i<=n;i++){
		if(a[i]==s[p]){
			flag=i;
			break;
		}
	}
	for(int i=1;i<=n;i++){
		if(i!=flag)now[a[i]-'a'].push(i);
	}
	Ans.push(s[flag]);
	char b=s[flag];
	while(now[b-'a'].size()){
		Ans.push(s[now[b-'a'].top()]);
		char k=s[now[b-'a'].top()];
		now[b-'a'].pop();
		b=k;
	}
	Ans.pop();
	while(Ans.size()){
		ans+=Ans.top();
		Ans.pop();
	}
	cout<<ans<<endl;
	return 0;
} 

回复

4 条回复,欢迎继续交流。

正在加载回复...