Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-08-05SRM300台を練習していく part7

SRM 316 InboxCleanup

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

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

シミュレーションやるだけ。


public class InboxCleanup {

	public int fewestClicks(String messages, int low, int high) {
		int ct = Integer.MAX_VALUE;
		int len = messages.length();
		for (int per = low ; per <= high ; per++) {
			int clicks = 0;
			int last = (len - 1) / per;
			for (int i = 0 ; i <= last ; i++) {
				String m = "";
				if (i == last) {
					m = messages.substring(i * per);
				} else {
					m = messages.substring(i * per, (i+1) * per);
					clicks++;
				}
				int sp = 0;
				for (int ma = 0 ; ma < m.length() ; ma++) {
					if (m.charAt(ma) == 'D') {
						sp++;
					}
				}
				if (sp >= 1) {
					clicks += 1 + Math.min(1 + m.length() - sp, sp);
				}
			}
			ct = Math.min(ct, clicks);
		}
		return ct;
	}
}