SRM285Div2,500

You have a sentence written entirely in a single row. You would like to split it into several rows by replacing some of the spaces with “new row” indicators. Your goal is to minimize the width of the longest row in the resulting text (“new row” indicators do not count towards the width of a row). You may replace at most Kspaces.

You will be given a String sentence and an int K. Split the sentence using the procedure described above and return the width of the longest row.

単一の行で書かれた文章がある。

[java]
import java.util.Arrays;
public class SentenceSplitting {
public int split(String sentence, int K) {
String[] words = sentence.split(" ");
System.out.println(Arrays.toString(words));
int[] words_num = new int[words.length];
for (int i = 0; i < words.length; i++) {
words_num[i] = words[i].length();
}
System.out.println(Arrays.toString(words_num));
int[] results = conbination(words_num, K);
System.out.println("ans="+results[results.length – 1]);
return results[results.length – 1];
}

private int[] conbination(int[] words_num, int K) {
if (words_num.length<=1) {
return words_num;
}
// 隣り合ったもので最小となるものを探し結合したい
int index = 0;
int min = 51;
for (int i = 1; i < words_num.length; i++) {
if (words_num[i – 1] + words_num[i] < min) {
min = words_num[i – 1] + words_num[i];
index = i;
}
}
System.out.print("index:" + index + ":");
int[] new_words_num = new int[words_num.length – 1];
for (int i = 0; i < index; i++) {
new_words_num[i] = words_num[i];
}
new_words_num[index – 1] = words_num[index – 1] + words_num[index]+1;
for (int i = index; i < new_words_num.length; i++) {
new_words_num[i] = words_num[i + 1];
}
// 結合終了
System.out.println(Arrays.toString(new_words_num));
if (new_words_num.length <= K + 1) {
Arrays.sort(new_words_num);
return new_words_num;
}
return conbination(new_words_num, K);
}
}

[/java]