问题 B: 字典序最小问题
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：外部导入
提交：40
解决：6
题目描述
给定长度为N的字符串S，要制造一个长度为N的字符串T。起初，T是一个空串，随后反复进行下列任意操作。
1.从S的头部删除一个字符，加到T的尾部
2.从S的尾部删除一个字符，加到T的尾部
目标是要构造字典序尽可能小的字符串T。

输入
第一行N；(1<=N<=2000)
第二行字符串S，字符串S只包含大写英文字母。

输出
字符串(每80字符就换一行)

样例输入 复制
6
ACDBCB
样例输出 复制
ABCBCD

#include<bits/stdc++.h>
using namespace std;
int n,sum=0;
deque<char>t,s;
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
    {
        char c;
        cin>>c;
        s.push_back(c);
    }
    while(!s.empty())
    {
        if(s.front()<s.back())
        {
            t.push_back(s.front());
            s.pop_front();
        }
        if(s.front()>s.back())
        {
            t.push_back(s.back());
            s.pop_back();
        }
        if(s.front()==s.back())
        {
            char c=s.front();
            if(s.size()==1){s.pop_back();t.push_back(c);}
            if(s.size()==2){t.push_back(c),t.push_back(c);s.pop_back(),s.pop_front();}
            if(s.size()>2)
            {
               s.pop_front();
               s.pop_back();
               if(s.front()<s.back()){t.push_back(c);s.push_back(c);}
               else {t.push_back(c);s.push_front(c);}   
            }
        }
    }
    while(!t.empty())
    {
        cout<<t.front();
        sum++;
        t.pop_front();
        if(sum==80)cout<<endl;
    }
    return 0;
} 

50分