社区讨论
玄关,求大佬调
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 条回复,欢迎继续交流。
正在加载回复...