POJ NO.3617 Best Cow Line（字典序最小问题）

问题描述：

给你一个长度为N的字符串S，让你按照字典序排序。

注意，输出时每80个字符就要换行！！！

题目链接：点击打开链接

思路：

比较S开头和末尾（以“ABCDEF”为例‘A’为开头，‘F’为末尾）的字符的大小，将小的排在第一位，以后的每个字符都要排在其后面。

如果遇到开头和末尾相等的情况就要比较下一位的大小（开头的后一位，末尾的前一位）。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f

using namespace std;
const int MAX = 2016;

int main()
{
    int n;
    char arr[MAX];
    while(scanf("%d", &n) == 1)
    {
        for(int i = 0; i < n; i++)
            cin >> arr[i];//避免将回车读进数组
        int a = 0, b = n - 1, cnt = 0;
        while(a <= b)
        {
            int flag = 0;
            for(int i = 0; a + i <= b; i++)
            {
                //如果前面和尾部相等那么就比较下一个字符，很关键的一步
                if(arr[a + i] < arr[b - i])
                {
                    flag = 1;
                    break;
                }
                else if(arr[a + i] > arr[b - i])
                    break;
            }
            if(flag)
                putchar(arr[a++]);
            else
                putchar(arr[b--]);
            //每80个字符就要换行
            if(++cnt == 80)
            {
                putchar('\n');
                cnt = 0;
            }
        }
        printf("\n");
    }
    return 0;
}