题目描述

题目链接：https://ac.nowcoder.com/acm/contest/625/C
小六喜欢两全其美的事情，今天就正好有一个这样的机会。

小六面前有两根管子，管子里面放满了数字为1到9的小球。每次取球时，小六会先选择一根管子，再从这根管子的某一侧（左侧或右侧）取出一个球。在满足取球规则的情况下，他可以任意顺序取出所有小球。假如小六依次取出的球的编号为a1,a2,⋯,ana1,a2,⋯,an，则他最后就得到了一个形如a1a2⋯ana1a2⋯an样的十进制数。

小六希望他的取球顺序所组成的数是最大的，你可以帮一下他吗？

输入描述:

第一行输入数据组数。T (T≤14)T (T≤14)接下来T行，每行输入两串只含1∼9
1∼9的数字，表示两根管子里的小球的数字。每根管子内至少含1个小球，且数量不超过40个。

输出描述:

对每一组数据，输出一行Case #x: A，其中x是数据组数编号（从1开始），A是小六能组成的最大的数。

示例1

输入

2
123456 123456
9876346789 9854894589

输出

Case #1: 665544332211
Case #2: 99998888776655498443

看到这题就想到双端队列，想到双端队列我就完了
用string，只需40h , 其实还能再短。

#include<bits/stdc++.h>
using namespace std;
int main() {
    freopen("in.txt","r",stdin);
    int n;
    scanf("%d",&n);
    string a,b,c,d,ans;
    for(int t=1;t<=n;t++) {
        cin>>a>>c;
        b.clear();
        d.clear();
        ans.clear();
        for(int i=a.size()-1; i>=0; i--)
            b+=a[i];
        for(int i=c.size()-1; i>=0; i--)
            d+=c[i];
        while(a.size()||c.size()) {
            if(a>=b&&a>=c&&a>=d) {
                ans+=a[0];
                a.replace(0,1,"");
                b.replace(b.size()-1,1,"");
            } else if(b>=a&&b>=c&&b>=d) {
                ans+=b[0];
                b.replace(0,1,"");
                a.replace(a.size()-1,1,"");
            } else if(c>=a&&c>=b&&c>=d) {
                ans+=c[0];
                c.replace(0,1,"");
                d.replace(d.size()-1,1,"");
            } else {
                ans+=d[0];
                d.replace(0,1,"");
                c.replace(c.size()-1,1,"");
            }
        }
        cout<<"Case #"<<t<<": "<<ans<<endl;
    }
    return 0;
}

思路由xhp提供