kmjp's blog

競技プログラミング参加記です

yukicoder : No.205 マージして辞書順最小

★2.5位の感じ?
http://yukicoder.me/problems/412

問題

N個のアルファベット小文字で構成される文字列S[i]が与えられる。

初期状態で空文字列であるTに対し、S[i]のうち1つを選んで先頭の文字を消し、Tの末尾に追加する、という処理をS[i]がすべて空になるまで繰り返す。

Tとして得られる辞書順最小の文字列を求めよ。

解法

蟻本 p45を見ると類題が出てくる。

まずS[i]の末尾にアルファベットより文字コード順で後の末尾文字を追加しておく。
あとはS[i]のうち辞書順で最小のものを選択する、という処理を貪欲に繰り返せばよい。

int N;
string S[60];
string T;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>S[i], S[i]+="{";
	
	while(1) {
		x=-1;
		FOR(i,N) if(S[i].size()>1) {
			if(x==-1 || S[x]>S[i]) x=i;
		}
		if(x==-1) break;
		
		T+=S[x][0];
		S[x]=S[x].substr(1);
	}
	
	cout<<T<<endl;
}

まとめ

★2にしては難しいし3でもしょうがないね。