ACM-贪心入门：字典序最小 POJ3617

为简化文章，原题请直接看原题链接

中文题意

输入一串字符串，每次从字符串的两端取一个字符，直至取完，构建成一个新的字符串。要求该字符串字典序最小。

输入

第1行给出整数 n，代表字符的个数
第2行到第n+1行，每行给出一个字符，这些字符按顺序构成字符串

输出

输出题目要求的字符串，每行最多输出该字符串的字符80个，某行不满80个字符则继续在该行输出字符。

示例输入

6
A
C
D
B
C
B

示例输出

ABCBCD

解决思路

1. 设输入的字符串为S,T为S的反转字符串，顺序刚好与S相反
2. 初始化S和T的当前位置为0
3. 重复以下步骤直至输出的字符个数达到n
4. 1 每次决定选择两端的哪个字符时,在各自的当前位置起始，比较S和T的字典序大小
5. 2 如果S比较小，则输出S的第一个字符，并使S的当前位置自增1
6. 3 否则输出T的第一个字符，并使T的当前位置自增1

   AC代码

#include<stdio.h>
#include<cstring>
using namespace std;
char s[2019],t[2019]; 
int main(){
    int n,l=0,r=0;
    scanf("%d",&n);
    for(int i =0;i<n;++i){
        scanf("%c",&s[2019]);
        scanf("%c",&s[i]);
    }
    for(int i =0;i<n;++i)t[i] = s[n-i-1];
    t[n]='\0';    
    for(int i =0;i<n;++i){
        int is = strcmp(s+l,t+r);
        if(is<0){
            printf("%c",s[l]);
            ++l;
        }else{
            printf("%c",t[r]);
            ++r;
        }
        if((i+1)%80==0)printf("\n");
    }
    return 0;
}