ข้อสอบท้ายค่าย 2 ปีการศึกษา 2566 ศูนย์ สอวน. มหาวิทยาลัยเทคโนโลยีพระจอมเกล้าธนบุรี ข้อ Justify

---

Author: kaopj

---

Problem

สรุปโจทย์

มีคำ \(N\) คำ(ให้ \(W_i\) แทนคำที่ \(i\)) โดยต้องการจัดคำพวกนี้เป็นบรรทัดๆ โดยแต่ละบรรทัดมีจำนวนตัวอักษรไม่เกิน \(M\)(มีกี่บรรทัดก็ได้) โดยมีเงื่อนไขในการจัดคำคือ: 1. การเรียงลำดับคำ คำที่ \(i\) ต้องมาก่อนคำที่ \(j\) เสมอถ้า \(i<j\) 2. คำทุกคำจะต้องถูกคั่นด้วยอักขระช่องว่าง (" ") เสมอ 3. ให้คำทางซ้ายสุด และคำทางขวาสุดของแต่ละบรรทัดอยู่ชิดขอบ (ถ้าหากในบรรทัดมีคำเดียว ให้ชิดซ้าย และใส่อักขระช่องว่าง (" ") ในที่เหลือของบรรทัดนั้น) 4. ถ้าหากมีพื้นที่เหลือ (ไม่สามารถใส่คำเพิ่มลงไปในบรรทัดได้) ให้เพิ่มขนาดของช่องว่างระหว่างคำแทน โดยให้ขนาดข่องว่างเท่ากันมากที่สุด ถ้าหากมีขนาดช่องว่างไม่เท่ากัน ให้ช่องว่างที่มีขนาดมากกว่าอยู่ทางซ้ายเสมอ 5. บรรทัดสุดท้าย คำทางขวาสุดไม่จำเป็นต้องอยู่ชิดขอบก็ได้ และให้ช่องว่างระหว่างคำมีขนาด 1 อักขระเท่านั้น

สิ่งที่ต้องทำ

หารูปแบบที่ได้ออกมาของคำที่จัดแล้ว

Constraints

\(1 \leq N \leq 200\)
\(1 \leq M \leq\) จำนวนตัวอักษรของคำที่ยาวที่สุด
\(1 \leq\) จำนวนตัวอักษรของคำ \(\leq 20\)

Prerequisites

• String

---

Solution

วิธีทำ

สังเกตว่า เราสามารถจัดคำทีละบรรทัดได้

โดยเราจะใส่คำไปในบรรทัดไปให้ได้มากที่สุดเท่าที่เป็นไปได้ก่อน แล้วจึงจัดคำโดยที่สมมติว่าเรามี \(k\) คำในบรรทัดนี้ คำที่ \(i\) แทนเป็น \(w_i\)

สมมติให้ จำนวนตัวอักษรที่เหลือ(ไม่นับ " " ที่อยู่ระหว่างคำ) เป็น \(c\) เนื่องจากเราอยากแบ่งระยะระหว่างคำให้เท่ากัน จะได้ว่าเราควรจะเพิ่มระยะระหว่างคำ \(\frac{c}{k-1}\) ครั้ง

แต่ว่า \(\frac{c}{k-1}\) อาจมีเศษเหลือได้ โดยเศษจะมีค่าเท่ากับ \(c \equiv c_0 \mod{k-1}\) โดยที่ \(0 \leq c_0 < k-1\) เนื่องจากให้ช่องว่างที่มีขนาดมากกว่าอยู่ทางซ้ายเสมอ จะได้ว่าต้องเพิ่มระยะระหว่างคำที่ \(j\) กับคำที่ \(j+1\) ไปอีก \(1\) ครั้ง โดยที่ \(1 \leq j \leq c_0\)

---

Code:

c2_kmutt_66_justify.cpp

#include <bits/stdc++.h>
using namespace std;

int32_t main() {
    // input
    int N,M;
    cin >> N >> M;
    vector<string> W(N),w;
    for (int i=0;i<N;i++) {
        cin >> W[i];
    }
    int cnt=0;
    for (int i=0;i<N;i++) {
        if (cnt==0) {
            cnt+=W[i].size();
        } else {
            cnt+=W[i].size()+1;
        }
        if (cnt>M) {
            if (w.size()==1) {
                cout << w[0];
                cnt=W[i].size();
                w.clear();
                w.push_back(W[i]);
            } else {
                int charcnt=0;
                for (auto j:w) {
                    charcnt+=j.size()+1;
                }
                charcnt-=1;
                int c=M-charcnt;
                int c_0=c%(w.size()-1);
                cnt=0;
                for (auto j:w) {
                    cout << j;
                    if (cnt!=w.size()-1) {
                        for (int p=0;p<c/(w.size()-1)+(cnt<c_0)+1;p++) {
                            cout << " ";
                        }
                    }
                    cnt++;
                }
                cnt=W[i].size();
                w.clear();
                w.push_back(W[i]);
            }
            cout << '\n';
        } else {
            w.push_back(W[i]);
        }
    }
    if (!w.empty()) {
        for (int i=0;i<w.size();i++) {
            cout << w[i];
            if (i!=w.size()-1) {
                cout << " ";
            }
        }
    }
}

Total Time Complexity

\(O(N)\)