2010 TCO Qualification Round 1 - GirlsAndBoys
問題
http://community.topcoder.com/stat?c=problem_statement&pm=7794&rd=14294
・男の子と女の子が並んでいる。
・このうち、男の子と女の子が隣に並んでいる並びをできるだけ少なくしたい。
・並びを変えるには、一回の操作で任意の２人を入れ替えることができる。
・このときの、最小の操作回数を求める。
解き方
・最小の並べ方はBBBGGGもしくはGGGBBBとなる並べ方になる。
・よって、上の２つの並べ方のうち操作回数が小さいものが答えになる。
コード
using namespace std;
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class GirlsAndBoys {
public: int sortThem(string row) {
int INF=1e+8,n=row.size();
int cost=INF;
int tmpcost=0,pos=0;
for(int letter=0;letter<n;letter++){
if(row[letter]!='B')continue;
tmpcost+=abs(letter-pos);
pos++;
}
cost=min(cost,tmpcost);
tmpcost=0,pos=0;
for(int letter=0;letter<n;letter++){
if(row[letter]!='G')continue;
tmpcost+=abs(letter-pos);
pos++;
}
cost=min(cost,tmpcost);
return cost;
}
};
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class GirlsAndBoys {
public: int sortThem(string row) {
int INF=1e+8,n=row.size();
int cost=INF;
int tmpcost=0,pos=0;
for(int letter=0;letter<n;letter++){
if(row[letter]!='B')continue;
tmpcost+=abs(letter-pos);
pos++;
}
cost=min(cost,tmpcost);
tmpcost=0,pos=0;
for(int letter=0;letter<n;letter++){
if(row[letter]!='G')continue;
tmpcost+=abs(letter-pos);
pos++;
}
cost=min(cost,tmpcost);
return cost;
}
};
