Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-16SRM373 (Practice)

SRM 373 StringFragmentation

|  SRM 373 StringFragmentation - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 373 StringFragmentation - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8087

  • 文字を小さくすればフレームに収まらないということはないはず
    • 二分探索しよう
public class StringFragmentation {
	public boolean ispossible(String[] words, int width, int height, int size) {
		int maxline = height / (2 * size);
		int from = 0 ;
		int len = words.length;
		int maxletters = width / (size+2);
		for (int i = 0 ; i < maxline ; i++) {
			int letters = 0;
			while (letters < maxletters && from < len) {
				if (letters == 0) {
					letters += words[from].length();  
				} else {
					letters += 1 + words[from].length();
				}
				from++;
			}
			if (letters > maxletters) {
				from--;
			}
		}
		return (from == len);
	}
	
	public int largestFontSize(String text, int width, int height) {
		String[] words = text.split(" ");
		int min = 7;
		int max = 100000000;
		for (int cur = 0 ; cur < 100 ; cur++) {
			int mid = (min + max) / 2;
			if (ispossible(words, width, height, mid)) {
				min = mid;
			} else {
				max = mid;
			}
		}
		return (min <= 7) ? -1 : min;
	}
}