问题标题: 酷町堂：2626

2626   挑选字符经验值：1200

题目描述 Description

现在有一个长度为N的字符串，每次可以从字符串的开头或者结尾挑选一个字符，加到一个新字符串后面，新字符串初始是空串，被挑选的字符要在原串里删除。要使最终的新字符串字典序最小，求出这个字典序最小的新字符串。每行最多输出80个字符。

字典序是单词按字母顺序排列的方法。例如，“B"的字典序大于"A”；“ABD"的字典序大于"ABC”。

输入描述 Input Description

第一行，一个整数，N
接下来N行，每行一个大写字母

输出描述 Output Description

输出字典序最小的新字符串

样例输入 Sample Input

6 A C D B C B

样例输出 Sample Output

ABCBCD

数据范围及提示 Data Size & Hint

N≤10,000,000

10分：

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;

int main(){
    int n;
    cin>>n;
    string s="";
    for(int i=1;i<=n;i++){
    	char c;
    	cin>>c;
    	s+=c;
    }
    int i=0,j=n-1;
    string ans="";
    while(i<=j){
        if(s[i]<s[j]){
            ans+=s[i];
            i++;
        }
        else{
            ans+=s[j];
            j--;
        }
    }
    for(int i=0;i<n;i++){
        if(i%80==1&&i>=81){
            cout<<endl;
        }
        cout<<ans[i];
    }
    return 0;
}

周明轩在2020-08-20 20:33:38追加了内容

#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
bool fun(string s) {
	if(s.size()<=1){
		return true;
	}
	if(s[0]!=s[s.size()-1]){
		return s[s.size()-1]<s[0];
	}
	return fun(s.substr(1,s.size()-2));
}
string alg(string s) {
	string t="";
	long long l=s.size();
	if(l<=1){
		return s;
	}
	if(fun(s)){
		return t+s[l-1]+alg(s.substr(0,l-1));
	}
	return t+s[0]+alg(s.substr(1,l-1));
}
int main() {
	string a="";
	char x;
	long long n;
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>x;
		a+=x;
	}
	string b=alg(a);
	for(long long i=0;i<b.size();i++){
		cout<<b[i];
		if((i+1)%80==0){
			cout<<endl;
		}
	}
	return 0;
}

Runtime Error 80