TCO11 Qual2 Easy(250) BlackWhiteMagic

TopCoder

BlackWhiteMagic

Wの個数をwとして、creatures[0..w]に含まれるBの個数をcとすると、少なくともc回は交換が必要。位置が間違っているものを、ソート後のWとBの境目に近いものから順に交換していけば、c回でソート可能。

#include <string>
#include <algorithm>
using namespace std;

class BlackWhiteMagic{public:
int count( string creatures )
{
    int w = (int)std::count(creatures.begin(),creatures.end(),'W');
    return (int)std::count(creatures.begin(),creatures.begin()+w,'B');
}};