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