项链(necklace)

项链(necklace)

测试数据来自 wjszez/1968

项链是由各种大小不同的字母水晶珠连接在一起制成的,相邻的字母水晶珠之间的连接并不是很好,有可能会由于项链自身的重量在任意的地方断开。项链一旦断开,你懂的,情况会很糟糕。因此,制作项链时,知道哪些点容易断开是很重要的。对于某个接点,如果前面是小的珠子,项链断裂的可能性要比前面是大珠子要大的多。爱动脑筋的卡卡西想要进一步测试项链的稳定性,所以他需要一个程序以便决定最容易断开的那个点。
字母水晶项链是由一串A = a1a2 ... am序列组成,m表示制成项链的珠子的个数。当项链围成一圈时,最后一个字母am就与a1连接在一起。第i个珠子比第j个珠子更容易断裂就是说序列aiai+1 ... ana1 ... ai-1的字典序小于序列ajaj+1 ... ana1 ... aj-1的字典序。序列a1a2 ... an的字典序小于序列b1b2 ... bn的字典序就是存在一个整数i,i<=n, 对于每个j(1 <= j < i)都要有aj=bj且ai < bi。聪明的你能测试出项链的稳定性
【输入】
两行,第一行为一个正整数m(10≤m≤10000),表示组成项链的字母序长度,第二行为组成项链的字母序。每个珠子由一个英语的小写字母表示(a-z),a < b ... z。
【输出】
一行,项链最坏连接处字母珠子的编号。例如i,A[i]就是n个可能断裂点的字典序最小的地方。如果有不止一个的解,输出最小的i。
【输入样例】
necklace.in
11
amandamanda
【输出样例】
necklace.out
11

样例说明:框起来的a是最易断裂之处。

信息

ID
2377
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者