poj 3617 - Dream_you_to_life的专栏 - 博客频道 - CSDN.NET

Description:
You have a string S that length is N and make a string T that length is N. At the beginning, length of S is zero. You can do either operation from below:

 - delete the first character of S and add it into the end of T
 - delete the last character of S and add it into the end of T
Make T as small as in dictionary order.
题目大概意思就是:给你一个字符串S，你能做的操作是从头或者从尾删除掉一个字符，并将删掉的这个字符放到一个目标串T(T初始长度为0)中，直到S长度为0为止，T最终要满足的是以字典序比较尽可能的小.

以字典序比较的性质来说，不论T后面的字符有多大，只要前方的字符够小就行了，所以，可以用贪心来做。

每次选择添加到T后面的字符时，将头和尾中较小者放到T的后面，但这里面有个问题就是如果头和尾此时相同，该怎么处理？具体的可以想下这两组数据:CCABCC和DDEFDD

思路：

将S和S反转后的字符串S'进行比较:

1. 如果S比较小，则从头删掉一个元素，并将其放到T的尾端。
2. 如果S'比较小，则从尾删掉一个元素，并将其放到T的尾端。
3. 如果S等于S'，两边删除都可以。

这题还有个地方需要注意的就是输出的时候，一行最多能有80个字符,意思就是：当你字符个数超过80时，每行只能输出80个字符(最后一行除外)。

Code from http://www.tuicool.com/articles/Erq2am

int N;
char S[MAX_N+1];

void solve()
{
  int count = 1;
  int a = 0,b = N-1;
  while(a <= b)
  {
    bool left = false;
    for(int i = 0;a+i<=b;i++)
    {
      if(S[a+i]<S[b-i])
      {
        left = true;
        break;
      }
      else if(S[a+i]>S[b-i])
      {
        left = false;
        break;
      }
    }
    
    if(left) putchar(S[a++]);
    else putchar(S[b--]);
    // PE????80???????????У? 
    count++;
    if(count>80){
      cout<<endl;
      count = 1;
    }
      
  }
}

int main()
{
  cin>>N;
  for(int i = 0;i<N;i++)
    cin>>S[i];
  solve();
  return 0;
}

http://blog.csdn.net/dream_you_to_life/article/details/9446085

1. int main()  
2. {  
3.     std::ios::sync_with_stdio(false);  
4.     int n,l,r,cnt=0;  
5.     string cow,tmp;  
6.     cin >> n ;  
7.     l = 0 , r = n-1;  
8.     while(n--)  
9.     {  
10.         cin >> tmp ;  
11.         cow +=tmp;  
12.     }  
13.     while(l<=r)  
14.     {  
15.         bool left=false;  
16.         for(int i=l,j=r;i<j;++i,--j)  
17.         {  
18.             if(cow[i]!=cow[j])  
19.             {  
20.                 left = cow[i] < cow[j];  
21.                 break;  
22.             }  
23.         }  
24.         ++cnt;  
25.         cout << ( left ? cow[l++] : cow[r--] ) << ( cnt%80 ? "" : "\n");  
26.     }  
27.     return 0;  
28. } 

Read full article from poj 3617 - Dream_you_to_life的专栏 - 博客频道 - CSDN.NET