2011 TCO Algorithm Qualification Round 2 easy
問題概要
WとBからなる文字列が与えられる。
長さがnである。
1~nまでの距離の文字の位置を入れ替えることができる。
それぞれの長さは一回しかつかえない。
最小何ステップで全てのWが全てのBの左側にできるか。
解法
貪欲
Wの数を数える。
そして、本来Wがあるべき位置にBがあった場合、文字列全体で一番右側のWと入れ替える。
この操作を続ける限り、同じ長さの入れ替えを二回することはない。
→よって、この方法で入れ替えられる。
最低でも、Wが本来ある位置のBをすべて動かさなければ、目的の並びを実現できない。
→よって、この方法が最小手
つまり、Wがあるべき場所のBの数を数えればよい。
ソース
#include<string> #define REP(i,b,n) for(int i=b;i<(int)n;i++) #define rep(i,n) REP(i,0,n) using namespace std; class BlackWhiteMagic { public: int count(string C){ int W = 0; rep(i, C.length()){ if(C[i] == 'W')W++; } int ans = 0; rep(i, W){ if(C[i] == 'B')ans++; } return ans; } };