学步园

题目描述

夏娜酱最喜欢菠萝包了，于是威尔艾米娜从天道宫下来买了一大堆菠萝包。夏娜酱先将这些菠萝包按某种顺序排成一列，然后给每个菠萝包起了个名字，名字都是单个 的大写字母A-Z。小白想检验一下夏娜酱的学习成果，要求夏娜酱以下两种方式将这些菠萝包重排为新序列，使这些菠萝包的名字组成的新序列字典序最小。

1.从原序列的前端取出一个菠萝包，放在新序列的尾端

2.从原序列的尾端取出一个菠萝包，放在新序列的尾端

注：字典序的比较如：ABCDE<BCDEA，   ABCDE<ABDCE。

聪明的夏娜酱已经完成这个任务了，现在，轮到你来造出这样的新序列了。

输入：

输入包含多组用例，每组用例占两行，在每组用例中，第一行为一个整数n（1<=n<=2000），第二行为一个只包含大写字母的原序列。

输出：

对每组用例，输出符合要求的新序列，每80个字符换一次行，当然串尾要换行。

分析：

光用脑子想感觉很简单，就是每次找两端的较小值放入新数组里。如果两端相等，就不断往里找，离较小值较近的一端放入新数组。

然而，实际上，具体编程的时候遇到了严重的问题， 就是如何考虑周全两个指针将要碰到一起甚至交错的时候的情况。

代码

#include <stdio.h>
#include <string.h>
#define CONTAIN 2005
void print(char *str);
int main()
{
	freopen("/home/langley/programe/sample.txt","r",stdin);
        int n = 0;//number of letters
	while(scanf("%d",&n) != EOF)
	{
	    char str[CONTAIN] = {0};//string of input
    	getchar();
    	for(int i = 0;i < n;i ++)
    	{
    		str[i] = getchar();
    	}
    	char display[CONTAIN] = {0};//string of output
    	int p = 0;//a whole varible as the index of display
    	int start = 0,end = strlen(str) - 1;//the range of the string
    	while(1)
    	{
    		if(str[start] != str[end])
    		{
    			if(str[start] < str[end])
    			{
    				display[p] = str[start];
    				start ++;
    			}
    			else
    			{
    				display[p] = str[end];
    				end --;
    			}
    		}
    		else
    		{
    			int temp_s = start,temp_e = end;
    			for( ;temp_s <= temp_e && str[temp_s] == str[temp_e] ;temp_s ++,temp_e --);
    			if(temp_s < temp_e)
    			{
    				if(str[temp_s] < str[temp_e])
    				{
    					display[p] = str[start];
    					start ++;
    				}
    				else if(str[temp_s] > str[temp_e])
    				{
    					display[p] = str[end];
    					end --;
    				}
    			}
    			else if(temp_s >= temp_e)//sys
    			{
    				display[p] = str[start];
    				start ++;
    			}
    		}
    		//No need to consider this much
    		/*if(start == end)
    		{
    			display[p+1] = str[start];
    			break;
    		}*/

    		if(start > end)//you could have put this in while();
    			break;
    		p ++;
    	}
		display[n] = 0;
    	print(display);
    }
	return 0;
}

void print(char *str)
{
   char *p = str;
   while(1)
   {
        for(int i = 0;i < 80 && *p != 0;i ++)
        {
            putchar(*p);
            p ++;
        }
        if(*p == 0)
            break;
        putchar(10);
    }
    putchar(10);
}

void print(char *str) 
{ 
   char *p = str; 
   while(1) 
   { 
      for(int i = 0;i < 80;i ++) 
      { 
          if(*p != 0) 
          { 
              putchar(*p); 
                p ++; 
          } 
          else if(*p == 0 ) 
          { 
                if(i != 0) 
                { 
                    putchar(10); 
                    return ; 
                } 
                else 
                    return ; 
          } 
     } 
}