正文

牛客——Rabbit的字符串

IP云
IP云V管理员/0 阅读
11/25
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目：

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述
Rabbit得到了一个字符串，她的好朋友xxx可以给这个字符串施加 一次 魔法。
魔法可以选择字符串的任一位置，并将该位置后面的所有字符 水平 拼接到串首。
例如：对于字符串abcde，可以通过施加魔法得到cdeab。
如果xxx通过施加魔法将字符串的字典序变得 严格 比之前的小，那么他将拿走这一字符串。
Rabbit想知道自己的字符串会不会被xxx拿走。

输入描述: 
第一行一个整数n,表示字符串的长度。

接下来一行一个长度为n的只由小写字母组成的字符串。

输出描述: 
如果Rabbit的字符串会被xxx拿走，输出“YES”。
否则输出“NO”。
(不输出引号)
示例1

输入 
5

cdeab

输出 
YES

说明 
xxx可以把e之后的部分“ab”放到串首，得到abcde，字典序比cdeab小，故将拿走字符串。

示例2

输入 
5

abcde

输出 
NO

备注: 
1≤n≤100000

字典序的说明：https://en.wikipedia.org/wiki/Alphabetical_order

分析：

第一次遇到这种题目，用的是字符串的最小表示法，我会单独写一篇博客介绍这个方法，这里我只介绍本题的做法。

首先，他给出的字典序的说明这个网站是不能用的，那么什么是字典序呢？

字典序按照我的理解就是像字典一样排版的序列，比如字典的第一页永远都是a开头的英文单词，如果遇到all和any这样的单词，他会根据第二位进行比较排序，如果第二位也一样就比较第三位以此类推直到表交出结果（不可能没有结果，如果没有就说明两个单词是一样的，ps：an和any肯定是an在前面）。

那么回到这道题目，如果xxx可以拿走这个字符串的条件就很明显了，他需要把字符串某一位置直到最后的字符串截取拼接到前面比如按来的大。比如abaab就可以拿走，而aabab则不可以。

abaab可以变成aabab，很明显要比原来的大，而aabab就是最大的排列方式了。

代码： 

 import java.io.BufferedReader;

 import java.io.IOException;

 import java.io.InputStreamReader;

 import java.io.StreamTokenizer;

 public class Main {

     static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

     static String next() throws IOException {cin.nextToken();return cin.sval;}

     static int nextInt() throws IOException {cin.nextToken();return (int)cin.nval;}

     public static void main(String args[]) throws IOException {

         int len=nextInt();

         String s=next();

         int res=res(s,len);

         if(res==0)

             System.out.println("NO");

         else

             System.out.println("YES");

     }

     public static int res(String c,int len) {

         int i=0,j=1,k=0;

         while(i<len&&j<len&&k<len) {

             if(c.charAt((i+k)%len)==c.charAt((j+k)%len))

                 k++;

             else if(c.charAt((i+k)%len)<c.charAt((j+k)%len)) {

                 j=j+k+1;

                 k=0;

             }

             else {

                 i=j+k;

                 j=i+1;

                 k=0;

             }

         }

         return i;

     }

 }

相关阅读

目录[+]