首页 > 代码库 > Best Cow Line 解题报告

Best Cow Line 解题报告

2024-07-05 10:30:03   227人阅读

  1. 题目链接: http://poj.org/problem?id=3617
  2. 题意: 已知一段长度为N的字符串,让你构造一个字典序最小的字符串.构造的规则如下:如果原始字符串的头部 < 原始字符串的尾部,则从原始字符串的头部删除该字符添加到新         的字符串的一个字符;如果头部 > 尾部则删除尾部的字符添加到新字符串中.
  3. 解题思路: 首先用两个索引记录首尾的位置,然后依次比较两者的值,若头部的值小则头部索引+1向后移动一位,若尾部的值小则尾部索引-1向前移动一位,这是当两个位置的值不一样的情况下的比较,也比较简单。  但是复杂的情况就是两者的值相等的情况,我看的参考书是《挑战程序设计竞赛》第2版人民邮电出版社,这是翻译的日本人写的一本书,书中讲到这个问题时,解释为两者相等时随便选前后皆可,而且书中给出的代码中也没分析两者的情况,在很多的blog中有人也说可以随便选取.   但是仔细想想并非如此!!!!  就拿书中给出的这个题的例子分析, 原始串为"ACDBCB" 去除首尾的A和B后就剩下 "CDBC"，若先选择首部的C 则剩下的4个字母的选择顺序为"CCBD",若选择尾部的C则剩下的4个字母的选择顺序为"CBCD" ,由此可见并不是随便选择的. 很显然如果两者的值相同的时候,必须继续比较两者的下一位的大小,但是要保证首部的索引要小于或等于尾部的索引!所以此题的难处就在于此,分清楚这个问题,此题就引刃而解了.但是分析下一位的时候可能会出现哪几种情况呢? 1 头部小选择头部 2 尾部小选择尾部 3 头尾继续相等,继续比较下一位. 但是注意极限状态,当首尾的索引相等的情况,说明从开始相等的部分开始是对称的(此时两个的索引是同一个值了,所以是奇数个的对称),既然有奇数个的对称就应该有偶数的对称(ACDDCB)次数会出现头尾的索引会交叉，当然是用另外的变量来代替(程序中的left 和right).所以此题就是要理清出具体的情况分类.而且这题是基于贪心策略的喔!每次选择最优的值呀!
  4. 解题代码:  下面的是我自己的代码,跟很多牛人的blog的代码在算法简便性上还是有很大差距,仅供参考(通过提交的结果看耗时太大还有待优化). 
     1 #include <stdio.h>
 2 #include <stdlib.h>
 3 int min(int x,int y)
 4 {
 5     if(x < y)
 6         return x;
 7     else
 8         return y;
 9 }
10 int main()
11 {
12     char *str = NULL,c,*res = NULL;
13     int n,i,j,t;
14     scanf("%d",&n);
15     str = malloc(sizeof(char)*n);
16     res = malloc(sizeof(char)*n);
17     for(i = 0; i < n; i++)
18     {
19         getchar();
20         scanf("%c",&c);
21         str[i] = c;
22     }
23 
24     i = 0;  //头部索引
25     j = n-1; //尾部索引
26     t = 0;
27     while(i <= j)  
28     {
29         if(str[i] < str[j])
30             res[t++] = str[i++];
31         else if(str[i] > str[j])
32             res[t++] = str[j--];
33         else if(str[i] == str[j])  // 分析两者相等的情况
34         {
35             int left = i,right = j;
36             while(str[left] == str[right] && left < right)  //如果下一位继续相等继续比较下一位
37             {
38                 left++;
39                 right--;
40             }
41             if(str[left] < str[right] || left == right)   //如果头部的值小或者比较到两者的索引相等了此时这个串中间是对称的了,前后均可!
42             {
43                 res[t++] = str[i++];
44 
45             }
46 
47             else if(str[left] > str[right])   //右边的小取右边
48             {
49                 res[t++] = str[j--];
50             }
51 
52     return 0;
53     }

     


联系
我们