首页 > 代码库 > 16级第二周寒假作业J题
16级第二周寒假作业J题
Favorite Donut
露露爱吃甜食。她最喜欢的食物是环形甜甜圈。每天她从同一个面包店买一个环形甜甜圈。环形甜甜圈由n个部分组成。每个部分具有其自身的糖度，甜度可以由从a到z（从低到高）的字母表示，并且环形甜甜圈可以以一个第i个字符 表示顺时针的第i个部分的糖度的字符串来表示。注意，z是最甜的，并且如果两个部分具有相同的糖度，则他们是一样甜的。
一旦露露吃了甜甜圈的一部分，她必须继续吃其未吃完的相邻部分，直到所有部分都吃完为止。因此，她在咬下后必须沿顺时针或逆时针吃完，所以有2n种方式吃有n个部分的环形甜甜圈。例如，露露有6种方式吃一个环形甜甜圈abc：abc，bca，cab，acb，bac，cba。露露喜欢吃最甜的部分，所以她实际上更喜欢以最大的字典序的方式。如果存在两个或更多个满足字典序最大的方式，则她将优选其起始部分下标最小的方式。如果两种方式从同一部分开始，则她将更喜欢以顺时针顺序食用甜甜圈。请计算吃最喜欢的甜甜圈的方式。
First line contain one integer T, which means the number of test case.
For each test case, the first line contains one integer n,n≤20000, which represents how many parts the ring donut has. The next line contains a string consisted of n lowercase alphabets representing the ring donut.
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).
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题