题解 P5329 【[SNOI2019]字符串】
P5329 [SNOI] 2019
本蒟蒻认为，这道题难度适中，排紫题有点过了
这题的代码超简单，而且是
Main idea
一看题目就发现要找规律（看到这种题目的本能反应），稍加思考即可发现：
如果后面有一个比前面大的字母，那么前面无论如何删都比后面的大，直接吧前面的放在答案数组的最后即可；
如果后面有一个比前面小的字母，那么前面无论如何删都比后面的小，直接吧前面的放在答案数组的最前即可；
然后由于我们一遇到比前面大的/小的，就判断，所以这个字符串一定只剩最后那一段相同的字母，特判即可。
如图（图丑，望谅解）
Code
只有二十一行呢
#include<bits/stdc++.h>
using namespace std;
int n,ans[1000010],id=1;
char c[1000010];
int main(){
cin>>n>>c+1;
int l=0,r=n+1;
for(int i=2;i<=n;i++){
if(c[i]>c[i-1]){
for(int j=i-1;j>=id;j--) ans[--r]=j;
id=i;
}
if(c[i]<c[i-1]){
for(int j=id;j<i;j++) ans[++l]=j;
id=i;
}
}
for(int i=id;i<=n;i++) ans[++l]=i;
for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
return 0;
}