题解：AT_abc409_d [ABC408D] String Rotation

## 题意分析

题目让我们求一个字符串中将一个子串向左旋转 1 位（其实就是将某一个字符插入到某一个位置）后能得到的字典序最小的字符串。

## 算法选取

这题其实是一道结论题，我先给一下结论：将字符串中第一个满足 $s_{pos}>s_{pos-1}$ 的位置记为 $k$，那么就是将 $s_k$ 插入到第一个满足 $s_{pos}>s_{k}$ 的位置（记为 $p$）前面，$k$ 不存在时就不动（相当于把一个字符做了旋转）。

这里我来证一下：首先，移动 $s_k$，一定是最优的。如果移动 $k$ 左边的位置会让字典序变大，一定不优；如果移动 $k$ 右边的，显然字典序要比移动 $k$ 大，因为 $s_k$ 一定比 $s_{k+1}$ 大，如果不比 $s_{k+1}$ 大，那 $k$ 不存在，有矛盾，所以一定比 $s_{k+1}$ 大。\
然后，插入到 $p$ 处也一定是最优的，如果插入到 $p$ 后面也一定不优，因为 $s_p$ 要比 $s_k$ 大，显然，插入到 $p$ 前面也不优，因为 $s_{p-1}$ 要比 $s_k$ 小。

所以，直接把 $s$ 用 `substr` 分成 $s_0\sim s_{k-1}$，$s_k$，$s_{k+1}\sim s_{p-1}$，$s_p\sim s_{n-1}$（注意这里是 0-based），再按 $s_0\sim s_{k-1}$，$s_{k+1}\sim s_{p-1}$，$s_k$，$s_p\sim s_{n-1}$ 拼起来即可。

## 优化

可以看 [CF 上的 ABC 讨论帖](https://codeforces.com/blog/entry/143567)盖得最高的那一楼，那位外国人采用了 `swap` 的写法，应该会更快，所以我们可以把 $s_k$ 向后 `swap` 到 $s_p$ 前面，当然也可以 `erase` 和 `insert`，~~但我不想写~~。

## code

### 优化前

```cpp
#include<bits/extc++.h>
using namespace std;
using namespace chrono;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
int t,l,p,i;
string s,tmp;
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		cin>>l>>s;
		if(l==1){
			cout<<s<<'\n';
			continue;
		}
		i=1;
		for(;s[i-1]<=s[i]&&i<s.length();i++);
		p=--i;
		for(;i<s.length()&&s[i]<=s[p];i++);
		cout<<s.substr(0,p)+s.substr(p+1,i-p-1)+s[p]+s.substr(i)<<'\n';
	}
	return 0;
}
```

### 优化后

```cpp
#include<bits/extc++.h>
using namespace std;
using namespace chrono;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
int t,l,p,i;
string s,tmp;
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	cin>>t;
	while(t--){
		cin>>l>>s;
		if(l==1){
			cout<<s<<'\n';
			continue;
		}
		i=0;
		for(;s[i]<=s[i+1]&&i<s.length();i++);
		for(;i<s.length()-1&&s[i]>=s[i+1];swap(s[i],s[i+1]),i++);
		cout<<s<<'\n';
	}
	return 0;
}
```

正在渲染内容...