自动搬运

查看原文

来自洛谷，原作者为

	zjwwjhy 这个家伙不懒，但还是什么都没留下

搬运于2025-08-24 22:09:37，当前版本为作者最后更新于2020-05-13 18:42:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

$P5329$ $[SNOI]$ $2019$

本蒟蒻认为，这道题难度适中，排紫题有点过了

这题的代码超简单，而且是$O(n)$的

$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;
}

应该是过的吧，不要出锅啊

求赞