题解：P13189 [GCJ 2016 #1A] The Last Word

yyz0526 · 2025-07-12 10:05:17 · 题解

题目大意：

一个由大写英文字母组成的字符串 S ，按顺序从中给出一个新字母，将其写在单词的开头或末尾，没有单词时直接写，根据字典序排序，并且需要排在最后，每次可将一个字母插入到最前面或最后面。

思路：

由于题目要求要从两端进行插入操作，所以我们可以用双端队列——deque。（deque讲解）整个字符串搜一遍，并且每次进行比较，并插入。也就是说时间复杂度只有 \Theta(T \times S) ，这个速度已经很快了。

代码：

#include<bits/stdc++.h>
using namespace std;
string s;
deque<char> q;
int main(){
    int T;
    scanf("%d",&T);
    for(int i=1;i<=T;i++){
        cin>>s;
        int len=s.length();
        for(int j=0;j<len;j++){
            if(q.empty()){ // 队列空无法比较，直接加入。 
                q.push_back(s[j]);
            } 
            else{
                if(q.front()<=s[j]){ // 注意 ≤ 和字典序。
                    q.push_front(s[j]);
                }
                else{
                    q.push_back(s[j]);
                }
            }
        }
        printf("Case #%d: ",i);
        while(!q.empty()){
            char p=q.front();
            printf("%c",p);
            q.pop_front();
        }
        printf("\n");
    }
    return 0;
}