import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _68 {
    static class Solution {
        public List<String> fullJustify(String[] words, int maxWidth) {
            //1. space的数量至少为 x = 单词数 -1;
            //2. 处理多余的空格
            //第 n个空格数 =(  剩余的空格 % x >= n ? 1 : 0 ) + 剩余的空格/x;
            int wordCount = 0;
            int curNum = 0;
            List<String> res = new ArrayList<>();
            int i = 0;
            while (curNum > 0 || i < words.length) {
                if ((i >= words.length && curNum > 0) || words[i].length() + curNum + wordCount > maxWidth) {
                    int reamin = maxWidth - curNum;
                    StringBuilder sb = new StringBuilder();
                    int j = 0;
                    for (j = i - wordCount; j < i - 1; j++) {
                        //二目运算符要注意优先级
                        int curSpace = (maxWidth - curNum) / (wordCount - 1) + ((maxWidth - curNum) % (wordCount - 1) >= j - (i - wordCount) + 1 ? 1 : 0);
                        //如果是最后一个的话，空格只有一位
                        if (i == words.length) {
                            curSpace = 1;
                        }
                        reamin -= curSpace;
                        sb.append(words[j]);
                        char[] ch = new char[curSpace];
                        Arrays.fill(ch, ' ');
                        sb.append(ch);
                    }
                    sb.append(words[j]);
                    if (reamin > 0) {
                        char[] ch = new char[reamin];
                        Arrays.fill(ch, ' ');
                        sb.append(ch);
                    }
                    res.add(sb.toString());
                    wordCount = 0;
                    curNum = 0;
                } else {
                    wordCount++;
                    curNum += words[i].length();
                    i++;
                }
            }
            return res;
        }
    }
}