POJ 3617 Best Cow Line

http://poj.org/problem?id=3617

贪心

注意贪心的策略只要策略对了贪心还是比较简单的

为使最终系列为尽量小的字典序

每次取我们都取最小的字母当相同时我们就比较第二个这样当取了这一个字母之后放出来的下一个可选字母又是比较小的

-->>推广之正序串反序串比较从较小的一头取字母

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 #include <time.h>
 5 #include <stdlib.h>
 6 
 7 //poj 3617 贪心策略 正序 反序 相比 取较小的一头的字符 题目理解有点难度
 8 using namespace std;
 9 
10 int N;
11 char cow[2015], newline[2015];
12 
13 void solve()
14 {
15     int a, b, l = 0;
16     a = 0;
17     b = N - 1;
18     while (a <= b)
19     {
20         int s = a, e = b;
21         bool get = false;
22         while (s <= b)
23         {
24             if (cow[s] < cow[e])
25             {
26                 newline[l++] = cow[a++];
27                 get = true;
28                 break;
29             }
30             else if (cow[s] > cow[e])
31             {
32                 newline[l++] = cow[b--];
33                 get = true;
34                 break;
35             }
36             s++;
37             e--;
38         }
39         if (!get)//说明正序倒序相同
40         {
41             newline[l++] = cow[a++];//随便取一个
42         }
43     }
44 }
45 int main()
46 {
47     freopen("in.txt", "r", stdin);
48     freopen("out.txt","w", stdout);
49     while (~scanf("%d", &N))
50     {
51         for (int i = 0; i < N; i++)
52         {
53             getchar();
54             scanf("%c", &cow[i]);
55         }
56         cow[N] = '';
57         solve();
58         newline[N] = '';
59         for (int i = 0; i < N;i ++)
60         {
61             putchar(newline[i]);
62             if (i+1 >= 80  && (i+1) % 80 == 0) putchar('
');
63         }
64     }
65 //    srand((unsigned) time(NULL));
66 //    for (int i = 0; i < 99; i++)
67 //    {
68 //        int t = rand() % 26 + 65;
69 //        printf("%c
",t);
70 //    }测试时使用的随机数
71     return 0;
72 }