POJ 3617 Best Cow Line(贪心)

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 using namespace std;
 5 int main()
 6 {
 7     char cow[2005];
 8     char New[2005];
 9     int n;
10     while(cin>>n)
11     {
12         getchar();
13         for(int i=0;i<n;i++)
14         {
15             cin>>cow[i];
16             getchar();
17         }
18         /*for(int i=0;i<n;i++)
19             cout<<cow[i];
20             cout<<endl;*/
21         int len=0;
22         int head=0,tail=n;
23         while(head!=tail)
24         {
25             /*cout<<head<<" "<<tail<<endl;
26             cout<<cow[head]<<" "<<cow[tail-1]<<endl;
27             getchar();*/
28             if(cow[head]>cow[tail-1])
29             {
30                 New[len]=cow[--tail];
31             }
32             else if(cow[head]<cow[tail-1])
33                 New[len]=cow[head++];
34             else
35             {
36                     int a=head,b=tail-1;
37                     while(a!=b)
38                     {
39                         if(cow[a]>cow[b])
40                         {
41                             New[len]=cow[--tail];
42                             break;
43                         }
44                         else if(cow[a]<cow[b])
45                         {
46                             New[len]=cow[head++];
47                             break;
48                         }
49                         else
50                         {
51                             if(a==b-1)
52                             {
53                                 New[len]=cow[head++];
54                                 break;
55                             }
56                             a++;
57                             b--;
58                         }
59                     }
60                     if(a==b)
61                     New[len]=cow[head++];
62             }
63             len++;
64         }
65         for(int i=0;i<n;i++)
66         {
67             cout<<New[i];
68             if((i+1)%80==0)
69             cout<<endl;
70         }
71         cout<<endl;
72     }
73     return 0;
74 }
View Code