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

题目大意：

一个由大写英文字母组成的字符串

S

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

思路：

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

\Theta(T \times S)

，这个速度已经很快了。

代码：

CPP

#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;
}

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

文章操作

题目大意：

思路：

代码：

相关推荐

评论

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