NOIP 普及组初赛 · NOIP 2012 普及组初赛试题 第 26 题

阅读程序写结果

#include <iostream>
#include <string>
using namespace std;
int n,i,j,ans;
string s;
char get(int i)
{
	if(i<n) return s[i];
	else return s[i-n];	
}
int main()
{
	cin>>s;
	n=s.size();
	ans=0;
	for(i=1;i<=n-1;i++)
	{
		for(j=0;j<=n-1;j++)
			if(get(i+j)<get(ans+j))
			{
				ans=i;
				break;	
			}
			else if(get(i+j)>get(ans+j)) break;
	}
	for(j=0;j<=n-1;j++) cout<<get(ans+j);
	cout<<endl;
	return 0;	
}

输入：CBBADADA

看到循环移位找字典序最小，先想 get 函数的回绕特性。

易错：把 get(i+j) 当成普通下标，忘记 i+j≥n 时自动回绕到开头。

考点：字符串循环移位｜字典序最小值

程序在做什么

读入字符串 s，将 s 首尾相接形成无限循环串。外层 i 从 1 到 n-1 枚举所有非原串的循环移位起始位置，内层 j 逐位比较当前候选 i 与已选最优 ans：若某位 i 更小则更新 ans=i 并跳出内层；若某位 i 更大则直接放弃当前 i。最后输出以 ans 为起点的循环串。