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] = '