题解：P12984 [GCJ 2022 #1A] Double or One Thing

思路

从左往右对字符串

S

进行高亮操作，使结果为所有可能的字符串中字典序最小的一个。其中高亮共有

3

种情况：

$S_i < S_{i+1}$ 为了让字典序更小，此处肯定需要进行高亮操作。
$S_i > S_{i+1}$ 与第 $1$ 种情况相反，此处不需要进行高亮操作。
$S_i = S_{i+1}$ 这种情况比较特殊，我们需要找到 $S_i$ 之后第一个不是 $S_i$ 的字符，这里称作 $S_k$ ，然后根据上两条规则将 $S_i$ 和 $S_k$ 进行比较，决定是否进行高亮操作。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int main(){
	int T;
	cin>>T;
	for(int i=1;i<=T;i++){
		s1="";
		s2="";
		cin>>s1;
		int len=s1.length();
		for(int j=0;j<len-1;j++){
			if(s1[j]<s1[j+1]){ // 第一种情况。
				s2+=s1[j];
				s2+=s1[j];
			}else if(s1[j]>s1[j+1]){ // 第二种情况。
				s2+=s1[j];
			}else{ // 第三种情况。
				int k=j;
				while(s1[j]==s1[k]){
					k++;
				}
				if(s1[j]<s1[k]){
					s2+=s1[j];
					s2+=s1[j];
				}else{
					s2+=s1[j];
				}
			}
		}
		s2+=s1[len-1]; // 加上最后一个没判断的字符。
		cout<<"Case #"<<i<<": "<<s2<<endl;
	}
	return 0;
}

题解：P12984 [GCJ 2022 #1A] Double or One Thing

文章操作

思路

代码

相关推荐

评论

题解：P12984 [GCJ 2022 #1A] Double or One Thing