换行算法行宽、中断点位置、后断点位置、上一个断点位置设计加权平均断点算法 C++代码示例

下面是一个简单的C++代码示例，实现了加权平均断点算法：

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// 计算行宽
int line_width(const vector<string>& words, int start, int end) {
    int width = 0;
    for (int i = start; i <= end; ++i) {
        width += words[i].size();
    }
    width += end - start; // 加上单词之间的空格
    return width;
}

// 计算中断点位置
int break_point(const vector<string>& words, int start, int end, int max_width) {
    int mid = (start + end) / 2; // 中间位置
    int width = line_width(words, start, mid);
    while (width > max_width && mid > start) {
        --mid;
        width = line_width(words, start, mid);
    }
    return mid;
}

// 计算后断点位置
int back_point(const vector<string>& words, int start, int end, int max_width) {
    int mid = (start + end) / 2; // 中间位置
    int width = line_width(words, mid + 1, end);
    while (width > max_width && mid < end) {
        ++mid;
        width = line_width(words, mid + 1, end);
    }
    return mid;
}

// 计算加权平均断点
int weighted_break_point(const vector<string>& words, int start, int end, int max_width,
                          int last_break_point) {
    int mid = break_point(words, start, end, max_width);
    int back = back_point(words, mid + 1, end, max_width);

    // 计算加权平均断点
    int weighted_mid = (mid * (back - last_break_point) + back * (mid - last_break_point)) /
                       (back - last_break_point + mid - last_break_point);

    return weighted_mid;
}

// 将单词列表按照最大行宽分行
vector<string> justify_text(const vector<string>& words, int max_width) {
    vector<string> lines;
    int start = 0;
    int end = words.size() - 1;
    int last_break_point = -1;

    while (start <= end) {
        // 计算加权平均断点
        int mid = weighted_break_point(words, start, end, max_width, last_break_point);

        // 将单词列表中断为两部分
        vector<string> line_words(words.begin() + start, words.begin() + mid + 1);
        lines.push_back("");
        for (const auto& word : line_words) {
            if (!lines.back().empty()) {
                lines.back() += " ";
            }
            lines.back() += word;
        }
        start = mid + 1;
        last_break_point = mid;
    }

    return lines;
}

int main() {
    vector<string> words = {"This", "is", "an", "example", "of", "text", "justification."};
    int max_width = 16;

    vector<string> lines = justify_text(words, max_width);

    for (const auto& line : lines) {
        cout << line << endl;
    }

    return 0;
}

该算法的时间复杂度为$O(nlogn)$，其中$n$为单词个数