题目描述：
题解：
这题$O(n)$。
首先把连续的相同字符缩在一起。
然后考虑字典序的比较是从前向后一位一位比，所以：
当$a[i]>a[i+1]$时，删$a[i]$一定比删$a[j](j>i)$更优；
当$a[i]<a[i+1]$时，删$a[j]$一定比删$a[i]$更优。
然后深搜$O(n)$。
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 1000050; char a[N]; int b[N],c[N],n,m; void dfs(int i) { if(i>m)return ; if(c[i]>c[i+1]) { for(int j=b[i];j<b[i+1];j++)printf("%d ",j); dfs(i+1); }else { dfs(i+1); for(int j=b[i];j<b[i+1];j++)printf("%d ",j); } } int main() { scanf("%d%s",&n,a+1); for(int i=1;i<=n;i++) if(a[i]!=a[i-1]) b[++m]=i,c[m]=a[i]; b[++m] = n+1; dfs(1); puts(""); return 0; }
原文：https://www.cnblogs.com/LiGuanlin1124/p/11130122.html
