問題
http://community.topcoder.com/stat?c=problem_statement&pm=8482&rd=10810
解き方
各スペースに挿入するアンダースコアの数の差は最大１なので、
スペースの数と挿入できるアンダースコアの数がわかれば
答えは一意に定まる。
コード
class UnderscoreJustification {
public:
string justifyLine(vector<string> words, int width) {
int n=words.size();
int len=0;
FORE(i,0,n)len+=words[i].size();
int s=width-len;
int num2=s%(n-1);
int num1=(n-1)-num2;
s/=(n-1);
string ret=words[0];
FORE(i,1,n){
if((num1>0 && num2==0) || (words[i][0]<='Z' && num1>0)){
FORE(j,0,s)ret+='_';
num1--;
}else{
FORE(j,0,s+1)ret+='_';
num2--;
}
ret+=words[i];
}
return ret;
}
};
public:
string justifyLine(vector<string> words, int width) {
int n=words.size();
int len=0;
FORE(i,0,n)len+=words[i].size();
int s=width-len;
int num2=s%(n-1);
int num1=(n-1)-num2;
s/=(n-1);
string ret=words[0];
FORE(i,1,n){
if((num1>0 && num2==0) || (words[i][0]<='Z' && num1>0)){
FORE(j,0,s)ret+='_';
num1--;
}else{
FORE(j,0,s+1)ret+='_';
num2--;
}
ret+=words[i];
}
return ret;
}
};