第十五届 四川省大学程序设计大赛
J. 余料建造
Cuber QQ 会给定一个初始长度为 n 的字符串 S 与一个初始为空的字符串 T ，你可以进行 n 次操作，每次
操作可以选择从 S 的头部或者尾部取出一个字符，并将其添加到 T 的尾部。
现在 Cuber QQ 想请你构造出字典序最小的 T。
Input
第一行一个整数n(1≤ n ≤ 2 × 1e6），表示字符串的长度。
第二行一个字符串 S，保证 S 中只包含大小写英文字母。
Output
一行一个字符串T，表示答案。
Example
| standard input | standard output |
|---|---|
| 6 | |
| ACDBCB | ABCBCD |
Note
对于两个字符串 S = s1 s2 … sn 以及 T = t1 t2 … tm，如果在 S 和 T 从左往右第一个出现不同的位置 x
上有 sx < tx，或者 S 是 T 的前缀目 S 的长度小于 T ，那么我们说 S 的字典序小于 T 的字典序。
code:
#include<iostream>
using namespace std;
int main()
{
int n;
string s;
cin >> n >> s;
for(int i = 0, j = n - 1; i <= j;)
{
if(s[i] < s[j])cout << s[i++];
else if(s[i] > s[j])cout << s[j--];
else{
int l = i, r = j;
char min = s[i];
while(l <= r && s[l] == s[r] && s[l] <= min){
min = s[l];
cout << s[l];
l++;
r--;
}
if(l > r) i = l;
else if(s[l] < s[r]) i = l;
else if(s[l] > s[r]) j = r;
else{
int t_l = l, t_r = r;
while(t_l <= t_r){
if(s[t_l] < s[t_r])
{
i = l;
break;
}else if(s[t_l] > s[t_r]){
j = r;
break;
}
t_l++;
t_r--;
}
if(t_l > t_r) i = l;
}
}
}
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
char[] s = scan.next().toCharArray();
int cnt = 0;
for(int i = 0, j = n - 1; i <= j;){
if(s[i] < s[j]) System.out.print(s[i++]);
else if(s[j] < s[i]) System.out.print(s[j--]);
else {
int l = i, r = j;
char min = s[i];
while (l <= r && s[l] == s[r] && s[l] <= min){
min = s[l];
System.out.print(s[l]);
l++;
r--;
}
if(l > r) i = l;
else if(s[l] < s[r]) i = l;
else if(s[r] < s[l]) j = r;
else {
int tl = l;
int tr = r;
while(tl <= tr){
if(s[tl] < s[tr]){
i = l;
break;
}
else if(s[tr] < s[tl]){
j = r;
break;
}
tl++;
tr--;
}
if(tl > tr) i = l;
}
}
}
}
}
