TopCoder SRM 373 Div1 Easy StringFragmentation

問題

単語の列が与えられる。
これをheight x widthの板に、順に書きたい。
同じ単語は同じ行に書かなければならない。
また、一行の中の単語と単語の間は一つのスペースで区切る。

最大でいくつの大きさのフォントで板に全ての単語を書けるか求めよ。
フォントの大きさは最低でも8以上でなくてはならない。
不可能な場合は-1を返せ。

ただし、大きさNのフォントの一文字は高さN*2,幅N+2を持つものとする。

制約条件

textの文字数≦50
height,width≦10000

方針

フォントのサイズを全て試してみる。
フォントのサイズを決めると、一行に入る文字数および、とれる最大の行数がわかるので、greedyに単語を書いていき、全てが収まるかを確かめればよい。

ソースコード

class StringFragmentation {
	public:
	int largestFontSize(string text, int width, int height) 
	{
		vi len;
		stringstream ss(text);
		while(ss>>text)len.pb(text.size());
		int n=len.size();
		
		for(int i=width;i>7;i--){
			int h=height/i/2, w=width/(i+2);
			int j=0,t=0,l=1;
			for(;j<n;j++){
				if(t+len[j]>w)t=0, l++;
				if(t==0&&len[j]>w)break;
				t+=len[j]+1;
			}
			if(j>=n&&l<=h)return i;
		}
		return -1;
	}
};