首页 > 代码库 > 16级第二周寒假作业J题

16级第二周寒假作业J题

Favorite Donut

TimeLimit: 1500/1000 MS (Java/Others)  MemoryLimit: 131072/131072 K (Java/Others)
64-bit integer IO format:%I64d
Problem Description

露露爱吃甜食。她最喜欢的食物是环形甜甜圈。每天她从同一个面包店买一个环形甜甜圈。环形甜甜圈由n个部分组成。每个部分具有其自身的糖度,甜度可以由从a到z(从低到高)的字母表示,并且环形甜甜圈可以以一个第i个字符 表示顺时针的第i个部分的糖度的字符串来表示。注意,z是最甜的,并且如果两个部分具有相同的糖度,则他们是一样甜的。

 

一旦露露吃了甜甜圈的一部分,她必须继续吃其未吃完的相邻部分,直到所有部分都吃完为止。因此,她在咬下后必须沿顺时针或逆时针吃完,所以有2n种方式吃有n个部分的环形甜甜圈。例如,露露有6种方式吃一个环形甜甜圈abc:abc,bca,cab,acb,bac,cba。露露喜欢吃最甜的部分,所以她实际上更喜欢以最大的字典序的方式。如果存在两个或更多个满足字典序最大的方式,则她将优选其起始部分下标最小的方式。如果两种方式从同一部分开始,则她将更喜欢以顺时针顺序食用甜甜圈。请计算吃最喜欢的甜甜圈的方式。

 

Input

First line contain one integer T,T20, which means the number of test case.

For each test case, the first line contains one integer n,n20000, which represents how many parts the ring donut has. The next line contains a string consisted of n lowercase alphabets representing the ring donut.

Output

You should print one line for each test case, consisted of two integers, which represents the starting point (from 1 to n) and the direction (0 for clockwise and 1 for counterclockwise).

SampleInput
2 0
4 0
SampleOutput
2 0
4 0

题目大意就是给定一个字符构成的环,在这个环中选定一个起点,顺时针或逆时针使得以选定点为起点的字符串字典序最大。如果有多个答案,优先选择使起点位置在原字符串中编号较小的,如果还有多个答案,优先选择顺时针。

思路:存两个二倍字符串,一个正向一个反向。对于正向字符串,用最小表示法找到最大字符串的最小下标ans1;对于反向字符串,用最大表示法找到最大字符串的最大下标ans2(难点)。然后将通过这两个起点得到的字符串分别保存起来,用函数strcmp比较一下。
哪个比较大,哪个下标就是正确答案。一样大的时候,比较一下两个起点的大小,比较小的是正确答案,如果还是一样大,则输出正向。还有一难点就是ans2要想办法转化成原字符串的下标。
附上我的两个函数,两个最小表示法
技术分享
 1 int zuixiao(char *A)
 2 {
 3     int i=0,j=1,T=0;
 4     while(i<n&&j<n)
 5     {
 6         T=0;
 7         while(A[i+T]==A[j+T]&&T<n)
 8             T++;
 9         if(T==n)
10             return min(i,j);
11             if(A[i+T]<A[j+T])
12                 if(i+T+1>j)
13                 i=i+T+1;
14             else
15                 i=j+1;
16             else if(j+T+1>i)
17                 j=j+T+1;
18             else j=i+1;
19     }
20     return min(i,j);
21 }
最小表示法找最小下标
技术分享
 1 int zuida(char *A)
 2 {
 3     int i=0,j=1,T=0;
 4     while(i<n&&j<n)
 5     {
 6         T=0;
 7         while(A[i+T]==A[j+T]&&T<n)
 8             T++;
 9             if(T==n)
10             {
11                 int len=abs(i-j);
12                 return n-len+i;
13             }//如果用下面的if就直接暴力找最大,
14         /*if(T==n)//保存较大下标,重新找
15         {
16             i=max(i,j);
17             j=i+1;
18         }*/
19         else
20         {
21             if(A[i+T]<A[j+T])
22                 if(i+T+1>j)
23                 i=i+T+1;
24                 else
25                 i=j+1;
26             else if(j+T+1>i)
27                 j=j+T+1;
28             else
29                 j=i+1;
30         }
31     }
32     return j>=n?i:j;
33 }
最小表示法找最大下标

 AC时间:15MS

16级第二周寒假作业J题