17.5 แบบฝึกหัด

เขียนแต่ละข้อเป็นไฟล์ใหม่ใน Code::Blocks รันแล้วเทียบกับผลลัพธ์ที่ต้องได้ให้ตรงทุกตัวอักษร รวมถึงช่องว่างและการขึ้นบรรทัด ติดจริงๆ ค่อยเปิดคำใบ้ และเปิดเฉลยหลังทำเสร็จแล้วเท่านั้น

ข้อ 1 ตะกร้าคืนหนังสือ

ระดับง่าย เวลาไม่เกิน 1 วินาที

ห้องสมุดมีตะกร้าคืนหนังสือ นักเรียนที่มาคืนหนังสือวางเล่มของตัวเองไว้บนสุดของกองในตะกร้า บรรณารักษ์จะหยิบหนังสือจากบนสุดไปเก็บขึ้นชั้นทีละหลายเล่ม ให้จำลองตะกร้าตามคำสั่ง Q คำสั่ง แต่ละคำสั่งเป็นแบบใดแบบหนึ่งต่อไปนี้ ตอนเริ่มตะกร้าว่าง

• RETURN t นักเรียนวางหนังสือชื่อ t ไว้บนสุดของกอง
• SHELVE k บรรณารักษ์หยิบหนังสือจากบนสุดออกไปทีละเล่มจนครบ k เล่ม ถ้าในตะกร้ามีไม่ถึง k เล่มให้หยิบจนหมด ให้พิมพ์ชื่อหนังสือที่หยิบตามลำดับที่หยิบในบรรทัดเดียว คั่นด้วยช่องว่างหนึ่งช่อง ถ้าตะกร้าว่างอยู่แล้วให้พิมพ์ EMPTY
• TOP พิมพ์ชื่อหนังสือที่อยู่บนสุดโดยไม่หยิบออก ถ้าตะกร้าว่างให้พิมพ์ EMPTY

ทำครบทุกคำสั่งแล้ว ให้พิมพ์จำนวนหนังสือที่ยังเหลือในตะกร้า

ข้อนี้ตั้งใจให้ฝึกย้ายวิธีจากข้อกองจานในบทที่ 14 มาใช้ stack ของ STL ที่ต่างคือของในกองเป็นข้อความ และหยิบทีละหลายเล่มในคำสั่งเดียว

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม Q โดยที่ 1 ≤ Q ≤ 100000

อีก Q บรรทัด บรรทัดละหนึ่งคำสั่งตามรูปแบบข้างบน ชื่อหนังสือ t ยาว 1 ถึง 20 ตัวอักษร ประกอบด้วยตัวอักษรภาษาอังกฤษตัวเล็ก ตัวเลข และขีด - ไม่มีช่องว่าง ชื่อซ้ำกันได้ และ 1 ≤ k ≤ 100000

ข้อมูลออก

สำหรับคำสั่ง SHELVE และ TOP แต่ละคำสั่ง ให้พิมพ์คำตอบหนึ่งบรรทัดตามลำดับของคำสั่ง บรรทัดสุดท้ายพิมพ์จำนวนหนังสือที่เหลือในตะกร้า

10
RETURN math-1
RETURN thai-novel
TOP
RETURN physics
SHELVE 2
RETURN atlas
SHELVE 5
TOP
SHELVE 1
RETURN comic

thai-novel
physics thai-novel
atlas math-1
EMPTY
EMPTY
1

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    stack<string> basket;
    for (int i = 0; i < q; i++) {
        string command;
        cin >> command;
        if (command == "RETURN") {
            string title;
            cin >> title;
            basket.push(title);
        } else if (command == "SHELVE") {
            int k;
            cin >> k;
            if (basket.empty()) {
                cout << "EMPTY\n";
            } else {
                for (int j = 0; j < k && !basket.empty(); j++) {
                    if (j > 0) {
                        cout << ' ';
                    }
                    cout << basket.top();
                    basket.pop();
                }
                cout << '\n';
            }
        } else {
            if (basket.empty()) {
                cout << "EMPTY\n";
            } else {
                cout << basket.top() << '\n';
            }
        }
    }
    cout << basket.size() << '\n';
    return 0;
}

ข้อ 2 ช่องขายตั๋ว

ระดับง่าย เวลาไม่เกิน 1 วินาที

ช่องขายตั๋วคอนเสิร์ตเปิดขายพร้อมตั๋ว S ใบ แฟนเพลงต่อแถวเดียว แต่ละคนบอกตอนเข้าแถวว่าอยากซื้อกี่ใบ พอถึงคิว ถ้าตั๋วเหลือพอเขาจะได้ครบตามที่ขอ ถ้าเหลือไม่พอเขาจะได้เท่าที่เหลือ ซึ่งอาจเป็น 0 ใบก็ได้ แล้วออกจากแถวไป ให้จำลองช่องขายตั๋วตามคำสั่ง Q คำสั่ง แต่ละคำสั่งเป็นแบบใดแบบหนึ่งต่อไปนี้ ตอนเริ่มไม่มีใครในแถว

• JOIN name t คนชื่อ name มาต่อท้ายแถว อยากซื้อ t ใบ
• SELL คนหัวแถวซื้อตั๋วแล้วออกจากแถว ให้พิมพ์ชื่อของเขา ช่องว่างหนึ่งช่อง และจำนวนตั๋วที่เขาได้ ถ้าไม่มีใครในแถวให้พิมพ์ EMPTY
• LAST พิมพ์ชื่อของคนท้ายแถว ถ้าไม่มีใครในแถวให้พิมพ์ EMPTY
• COUNT พิมพ์จำนวนคนที่ยังอยู่ในแถว ช่องว่างหนึ่งช่อง และจำนวนตั๋วที่ยังเหลือ

ข้อนี้ตั้งใจให้ฝึกย้ายวิธีจากข้อแถวรถไฟเหาะในบทที่ 14 มาใช้ queue ของ STL ที่ต่างคือแต่ละคนในแถวมีสองค่า และจำนวนตั๋วใหญ่เกิน int

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม S และ Q คั่นด้วยช่องว่าง โดยที่ 0 ≤ S ≤ 10¹⁵ และ 1 ≤ Q ≤ 100000

อีก Q บรรทัด บรรทัดละหนึ่งคำสั่งตามรูปแบบข้างบน ชื่อ name ยาว 1 ถึง 15 ตัวอักษรภาษาอังกฤษ ไม่มีช่องว่าง และอาจซ้ำกันได้ จำนวนตั๋วที่ขอ t เป็นจำนวนเต็ม 1 ≤ t ≤ 1000000000

ข้อมูลออก

สำหรับคำสั่ง SELL LAST และ COUNT แต่ละคำสั่ง ให้พิมพ์คำตอบหนึ่งบรรทัดตามลำดับของคำสั่ง

10 9
JOIN Ploy 4
JOIN Krit 3
JOIN Mint 5
LAST
SELL
SELL
COUNT
SELL
SELL

Mint
Ploy 4
Krit 3
1 3
Mint 3
EMPTY

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long tickets;
    int q;
    cin >> tickets >> q;
    queue<pair<string, int>> line;
    for (int i = 0; i < q; i++) {
        string command;
        cin >> command;
        if (command == "JOIN") {
            string name;
            int want;
            cin >> name >> want;
            line.push({name, want});
        } else if (command == "SELL") {
            if (line.empty()) {
                cout << "EMPTY\n";
            } else {
                auto fan = line.front();
                line.pop();
                long long got = min((long long)fan.second, tickets);
                tickets -= got;
                cout << fan.first << ' ' << got << '\n';
            }
        } else if (command == "LAST") {
            if (line.empty()) {
                cout << "EMPTY\n";
            } else {
                cout << line.back().first << '\n';
            }
        } else {
            cout << line.size() << ' ' << tickets << '\n';
        }
    }
    return 0;
}

ข้อ 3 ชั้นวางขนมปัง

ระดับง่าย เวลาไม่เกิน 1 วินาที

ร้านเบเกอรี่มีชั้นวางขนมปังยาวหนึ่งชั้น ขนมปังทุกชิ้นมีหมายเลขรอบอบติดไว้ ชั้นเรียงจากชิ้นที่อบนานที่สุดทางซ้าย ไปจนถึงชิ้นที่อบล่าสุดทางขวา ให้จำลองชั้นวางตามคำสั่ง Q คำสั่ง แต่ละคำสั่งเป็นแบบใดแบบหนึ่งต่อไปนี้ ตอนเริ่มชั้นว่าง

• BAKE x ขนมปังหมายเลข x เพิ่งอบเสร็จ วางไว้ขวาสุดของชั้น
• FOUND x พนักงานเจอขนมปังหมายเลข x ตกค้างอยู่หลังร้าน มันเก่ากว่าทุกชิ้นบนชั้น จึงวางไว้ซ้ายสุดของชั้น
• FRESH ลูกค้าหยิบชิ้นที่ใหม่ที่สุด คือชิ้นขวาสุด ให้พิมพ์หมายเลขของมัน ถ้าชั้นว่างให้พิมพ์ EMPTY
• SALE ร้านขายลดราคาชิ้นที่เก่าที่สุด คือชิ้นซ้ายสุด ให้พิมพ์หมายเลขของมัน ถ้าชั้นว่างให้พิมพ์ EMPTY
• CHECK i ผู้จัดการถามว่าชิ้นที่ i นับจากซ้าย (ชิ้นซ้ายสุดคือชิ้นที่ 1) คือหมายเลขอะไร โดยไม่หยิบออก ถ้าชั้นมีขนมปังไม่ถึง i ชิ้นให้พิมพ์ NONE

ทำครบทุกคำสั่งแล้ว ให้พิมพ์จำนวนขนมปังที่ยังเหลือบนชั้น

ข้อนี้ตั้งใจให้ฝึกย้ายวิธีจากข้อสำรับไพ่ของนักมายากลในบทที่ 14 มาใช้ deque ของ STL ที่ต่างคือต้องดูชิ้นที่ i นับจากซ้ายได้ด้วย

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม Q โดยที่ 1 ≤ Q ≤ 200000

อีก Q บรรทัด บรรทัดละหนึ่งคำสั่งตามรูปแบบข้างบน โดยที่ 1 ≤ x ≤ 1000000000 และ 1 ≤ i ≤ 1000000000

ข้อมูลออก

สำหรับคำสั่ง FRESH SALE และ CHECK แต่ละคำสั่ง ให้พิมพ์คำตอบหนึ่งบรรทัดตามลำดับของคำสั่ง บรรทัดสุดท้ายพิมพ์จำนวนขนมปังที่เหลือบนชั้น

11
BAKE 101
BAKE 102
FOUND 95
CHECK 1
CHECK 3
CHECK 4
FRESH
SALE
BAKE 103
CHECK 2
SALE

95
102
NONE
102
95
103
101
1

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    deque<int> shelf;
    for (int k = 0; k < q; k++) {
        string command;
        cin >> command;
        if (command == "BAKE") {
            int x;
            cin >> x;
            shelf.push_back(x);
        } else if (command == "FOUND") {
            int x;
            cin >> x;
            shelf.push_front(x);
        } else if (command == "FRESH") {
            if (shelf.empty()) {
                cout << "EMPTY\n";
            } else {
                cout << shelf.back() << '\n';
                shelf.pop_back();
            }
        } else if (command == "SALE") {
            if (shelf.empty()) {
                cout << "EMPTY\n";
            } else {
                cout << shelf.front() << '\n';
                shelf.pop_front();
            }
        } else {
            int i;
            cin >> i;
            if (i > (int)shelf.size()) {
                cout << "NONE\n";
            } else {
                cout << shelf[i - 1] << '\n';
            }
        }
    }
    cout << shelf.size() << '\n';
    return 0;
}

ข้อ 4 ปุ่ม undo

ระดับกลาง เวลาไม่เกิน 1 วินาที

โปรแกรมพิมพ์ข้อความบนโทรศัพท์รุ่นหนึ่งพิมพ์ได้ทีละคำ และมีปุ่ม undo ให้ย้อนการแก้ไข ตอนเริ่มข้อความว่าง ผู้ใช้กดคำสั่ง Q ครั้ง แต่ละคำสั่งเป็นแบบใดแบบหนึ่งต่อไปนี้

• TYPE w พิมพ์คำ w ต่อท้ายข้อความ
• DELETE ลบคำสุดท้ายของข้อความ ถ้าข้อความว่างอยู่ คำสั่งนี้ไม่มีผลอะไร และไม่นับเป็นการแก้ไข
• UNDO ย้อนการแก้ไขครั้งล่าสุดที่ยังไม่ถูกย้อน การแก้ไขคือ TYPE หรือ DELETE ที่มีผลจริง ย้อน TYPE คือเอาคำที่พิมพ์ออก ย้อน DELETE คือเอาคำที่ถูกลบกลับมาต่อท้าย กด UNDO ติดกันหลายครั้งจะย้อนจากการแก้ไขล่าสุดไปหาเก่าสุดทีละครั้ง ถ้าไม่มีการแก้ไขเหลือให้ย้อน คำสั่งนี้ไม่มีผลอะไร คำสั่ง UNDO เองไม่ใช่การแก้ไข จึงย้อนไม่ได้
• LAST พิมพ์คำสุดท้ายของข้อความ ถ้าข้อความว่างให้พิมพ์ EMPTY

ทำครบทุกคำสั่งแล้ว ให้พิมพ์ข้อความทั้งหมด

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม Q โดยที่ 1 ≤ Q ≤ 200000

อีก Q บรรทัด บรรทัดละหนึ่งคำสั่งตามรูปแบบข้างบน คำ w ยาว 1 ถึง 10 ตัวอักษร เป็นตัวอักษรภาษาอังกฤษตัวเล็กเท่านั้น

ข้อมูลออก

สำหรับคำสั่ง LAST แต่ละคำสั่ง ให้พิมพ์คำตอบหนึ่งบรรทัดตามลำดับ

บรรทัดสุดท้ายพิมพ์ข้อความทั้งหมด คำคั่นด้วยช่องว่างหนึ่งช่อง ถ้าข้อความว่างให้พิมพ์ EMPTY

9
TYPE i
TYPE like
TYPE cats
DELETE
TYPE dogs
LAST
UNDO
UNDO
LAST

dogs
cats
i like cats

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    vector<string> text;
    stack<pair<char, string>> history;
    for (int i = 0; i < q; i++) {
        string command;
        cin >> command;
        if (command == "TYPE") {
            string word;
            cin >> word;
            text.push_back(word);
            history.push({'T', word});
        } else if (command == "DELETE") {
            if (!text.empty()) {
                history.push({'D', text.back()});
                text.pop_back();
            }
        } else if (command == "UNDO") {
            if (!history.empty()) {
                auto change = history.top();
                history.pop();
                if (change.first == 'T') {
                    text.pop_back();
                } else {
                    text.push_back(change.second);
                }
            }
        } else {
            if (text.empty()) {
                cout << "EMPTY\n";
            } else {
                cout << text.back() << '\n';
            }
        }
    }
    if (text.empty()) {
        cout << "EMPTY\n";
    }
    for (int i = 0; i < (int)text.size(); i++) {
        cout << text[i] << (i + 1 < (int)text.size() ? ' ' : '\n');
    }
    return 0;
}

ข้อ 5 ปุ่ม back และ forward

ระดับกลาง เวลาไม่เกิน 1 วินาที

เว็บเบราว์เซอร์มีปุ่ม back และปุ่ม forward ตอนเปิดโปรแกรม หน้าแรกที่เปิดอยู่คือ home ผู้ใช้ทำ Q อย่างตามลำดับ แต่ละอย่างเป็นแบบใดแบบหนึ่งต่อไปนี้

• VISIT p เปิดหน้า p จากหน้าปัจจุบัน หน้าปัจจุบันถูกจำไว้ให้ back กลับมาได้ และประวัติ forward ทั้งหมดถูกล้างทิ้ง แม้ p จะเป็นชื่อเดียวกับหน้าปัจจุบันก็นับเป็นการเปิดหน้าใหม่
• BACK กลับไปหน้าล่าสุดที่จากมา หน้าปัจจุบันถูกจำไว้ให้ forward กลับมาได้ ถ้าไม่มีหน้าให้กลับ ไม่มีอะไรเกิดขึ้น
• FORWARD ไปข้างหน้ากลับสู่หน้าล่าสุดที่เพิ่งกด back ออกมา หน้าปัจจุบันถูกจำไว้ให้ back กลับมาได้ ถ้าไม่มีหน้าให้ไป ไม่มีอะไรเกิดขึ้น

หลังทำแต่ละอย่าง ให้บอกว่าตอนนี้เปิดหน้าไหนอยู่

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม Q โดยที่ 1 ≤ Q ≤ 200000

อีก Q บรรทัด บรรทัดละหนึ่งอย่างตามรูปแบบข้างบน ชื่อหน้า p ยาว 1 ถึง 20 ตัวอักษร ประกอบด้วยตัวอักษรภาษาอังกฤษตัวเล็ก ตัวเลข และจุด ไม่มีช่องว่าง

ข้อมูลออก

Q บรรทัด บรรทัดที่ i คือชื่อหน้าที่เปิดอยู่หลังทำอย่างที่ i

12
VISIT news
VISIT sport
VISIT football
BACK
BACK
FORWARD
VISIT tennis
FORWARD
BACK
BACK
BACK
BACK

news
sport
football
sport
news
sport
tennis
tennis
sport
news
home
home

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> q;
    stack<string> back_pages, forward_pages;
    string current = "home";
    for (int i = 0; i < q; i++) {
        string command;
        cin >> command;
        if (command == "VISIT") {
            string page;
            cin >> page;
            back_pages.push(current);
            current = page;
            while (!forward_pages.empty()) {
                forward_pages.pop();
            }
        } else if (command == "BACK") {
            if (!back_pages.empty()) {
                forward_pages.push(current);
                current = back_pages.top();
                back_pages.pop();
            }
        } else {
            if (!forward_pages.empty()) {
                back_pages.push(current);
                current = forward_pages.top();
                forward_pages.pop();
            }
        }
        cout << current << '\n';
    }
    return 0;
}

ข้อ 6 ลูกแก้วสีเดียวกัน

ระดับกลาง เวลาไม่เกิน 1 วินาที

ในเกมลูกแก้วเกมหนึ่ง ลูกแก้วหลายสีวางเรียงกันเป็นแถวเดียวบนราง ถ้ามีลูกแก้วสองลูกที่อยู่ติดกันและสีเดียวกัน ทั้งสองลูกจะแตกหายไป แล้วลูกที่อยู่ทางซ้ายและทางขวาของคู่นั้นเลื่อนมาชิดกัน ซึ่งอาจทำให้เกิดคู่สีเดียวกันคู่ใหม่ แตกต่อกันไปเรื่อยๆ จนไม่มีลูกแก้วสองลูกที่ติดกันสีเดียวกันเหลืออยู่

ถ้ามีหลายคู่ให้แตกพร้อมกัน จะให้คู่ไหนแตกก่อนก็ได้ผลสุดท้ายเหมือนกันเสมอ ให้หาว่าลูกแก้วแตกไปทั้งหมดกี่คู่ และเหลือลูกแก้วสีอะไรบ้างเรียงจากซ้ายไปขวา

ตัวอย่างเช่น abccbd คู่ cc แตกก่อนเหลือ abbd แล้วคู่ bb ที่เพิ่งมาชิดกันแตกต่อ เหลือ ad รวมแตกไป 2 คู่

ข้อมูลเข้า

บรรทัดเดียว เป็นสีของลูกแก้วเรียงจากซ้ายไปขวา แต่ละสีแทนด้วยตัวอักษรภาษาอังกฤษตัวเล็กหนึ่งตัว ยาว 1 ถึง 1000000 ตัวอักษร

ข้อมูลออก

บรรทัดแรกพิมพ์จำนวนคู่ที่แตก

บรรทัดที่สองพิมพ์สีของลูกแก้วที่เหลือเรียงจากซ้ายไปขวาติดกันโดยไม่มีช่องว่าง ถ้าไม่เหลือลูกแก้วเลยให้พิมพ์ EMPTY

abccbd

2
ad

xyyxzz

3
EMPTY

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string marbles;
    cin >> marbles;
    string rail;
    int pairs = 0;
    for (char c : marbles) {
        if (!rail.empty() && rail.back() == c) {
            rail.pop_back();
            pairs++;
        } else {
            rail.push_back(c);
        }
    }
    cout << pairs << '\n';
    if (rail.empty()) {
        cout << "EMPTY\n";
    } else {
        cout << rail << '\n';
    }
    return 0;
}

ข้อ 7 เครื่องพิมพ์ผลัดกันพิมพ์

ระดับยาก เวลาไม่เกิน 1 วินาที

ห้องคอมพิวเตอร์มีเครื่องพิมพ์ใช้ร่วมกันหนึ่งเครื่อง วันนี้มีงานพิมพ์ส่งมา N งาน งานที่ i ส่งมาถึงที่วินาทีที่ a_i และยาว p_i หน้า เครื่องพิมพ์ได้วินาทีละหนึ่งหน้า เพื่อไม่ให้งานยาวงานเดียวกันคนอื่นไว้นาน เครื่องจะพิมพ์งานหนึ่งติดต่อกันได้ไม่เกิน K หน้าต่อรอบ แล้วต้องสลับไปงานอื่น เครื่องทำงานตามกฎนี้

• งานที่ส่งมาถึงจะต่อท้ายคิว ถ้าหลายงานมาถึงเวลาเดียวกัน งานที่อยู่ก่อนในข้อมูลเข้าต่อคิวก่อน
• เมื่อเครื่องว่าง ถ้าคิวมีงาน เครื่องหยิบงานหัวคิวมาพิมพ์ติดต่อกัน K หน้า หรือเท่าที่งานนั้นเหลือถ้าเหลือน้อยกว่า K หน้า ถ้าคิวว่าง เครื่องรอจนกว่าจะมีงานส่งมาถึง
• เมื่อพิมพ์จบหนึ่งรอบที่วินาทีที่ T ให้งานทุกงานที่ส่งมาถึงภายในวินาทีที่ T รวมถึงที่มาถึงตรงวินาทีที่ T พอดี ต่อท้ายคิวให้เรียบร้อยก่อน จากนั้นถ้างานที่เพิ่งพิมพ์ยังเหลือหน้า งานนั้นกลับไปต่อท้ายคิว ถ้าไม่เหลือแล้ว งานนั้นเสร็จที่วินาทีที่ T

ให้หาว่างานแต่ละงานเสร็จที่วินาทีที่เท่าไร

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ K คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 100000 และ 1 ≤ K ≤ 1000000000

อีก N บรรทัด บรรทัดที่ i มีจำนวนเต็ม a_i และ p_i คั่นด้วยช่องว่าง โดยที่ 0 ≤ a₁ ≤ a₂ ≤ ... ≤ a_N ≤ 1000000000 และ 1 ≤ p_i ≤ 1000000000

รับประกันว่าจำนวนรอบที่เครื่องพิมพ์ทั้งหมดรวมกันไม่เกิน 2000000 รอบ

ข้อมูลออก

N บรรทัด บรรทัดที่ i คือวินาทีที่งานที่ i พิมพ์เสร็จ

4 3
0 5
1 2
2 4
8 1

10
5
12
11

2 5
0 3
10 4

3
14

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> arrive(n), pages_left(n);
    for (int i = 0; i < n; i++) {
        cin >> arrive[i] >> pages_left[i];
    }
    vector<long long> finish(n);
    queue<int> waiting;
    long long now = 0;
    int next = 0;
    int done = 0;
    while (done < n) {
        if (waiting.empty()) {
            now = max(now, (long long)arrive[next]);
        }
        while (next < n && arrive[next] <= now) {
            waiting.push(next);
            next++;
        }
        int job = waiting.front();
        waiting.pop();
        int printed = min(pages_left[job], k);
        now += printed;
        pages_left[job] -= printed;
        while (next < n && arrive[next] <= now) {
            waiting.push(next);
            next++;
        }
        if (pages_left[job] > 0) {
            waiting.push(job);
        } else {
            finish[job] = now;
            done++;
        }
    }
    for (int i = 0; i < n; i++) {
        cout << finish[i] << '\n';
    }
    return 0;
}

ข้อ 8 สูงสุดในรอบกี่วัน

ระดับยาก เวลาไม่เกิน 1 วินาที

เขื่อนแห่งหนึ่งวัดระดับน้ำวันละครั้ง ติดต่อกัน N วัน วันที่ i วัดได้ h_i มิลลิเมตร ข่าวชอบพาดหัวว่า "ระดับน้ำวันนี้สูงสุดในรอบ X วัน" ซึ่งหมายถึงวันนี้กับอีก X - 1 วันก่อนหน้าที่ติดกัน รวม X วัน ทุกวันในช่วงนั้นมีระดับน้ำไม่เกินระดับของวันนี้ และ X มากที่สุดเท่าที่เป็นไปได้ ถ้าเมื่อวานระดับน้ำสูงกว่าวันนี้ X จะเป็น 1 เพราะนับแค่วันนี้วันเดียว

ให้หา X ของทุกวัน

ข้อนี้กลับด้านของข้อตึกที่สูงกว่าหลังแรกในบทที่ 14 ข้อนั้นมองไปทางขวา ข้อนี้มองย้อนไปทางซ้าย และนับวันที่สูงเท่ากันรวมในช่วงด้วย ตั้งใจให้ฝึกเขียน monotonic stack ด้วย stack ของ STL แล้วระวังเครื่องหมายเทียบให้ตรงกับโจทย์

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N โดยที่ 1 ≤ N ≤ 1000000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ h₁ ถึง h_N คั่นด้วยช่องว่าง โดยที่ 1 ≤ h_i ≤ 1000000000

ข้อมูลออก

บรรทัดเดียว มีจำนวนเต็ม N ตัวคั่นด้วยช่องว่างหนึ่งช่อง ตัวที่ i คือ X ของวันที่ i

8
120 110 115 130 125 125 140 100

1 1 2 4 1 2 7 1

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> level(n);
    for (int i = 0; i < n; i++) {
        cin >> level[i];
    }
    stack<int> higher;
    for (int i = 0; i < n; i++) {
        while (!higher.empty() && level[higher.top()] <= level[i]) {
            higher.pop();
        }
        int days;
        if (higher.empty()) {
            days = i + 1;
        } else {
            days = i - higher.top();
        }
        cout << days << (i + 1 < n ? ' ' : '\n');
        higher.push(i);
    }
    return 0;
}

ข้อ 9 สะพานแกว่ง

ระดับยาก เวลาไม่เกิน 1 วินาที

เครื่องวัดแรงสั่นสะเทือนบนสะพานบันทึกค่าเป็นจำนวนเต็มทุกมิลลิวินาที รวม N ค่า ค่าติดลบได้ เพราะสะพานแกว่งได้ทั้งสองทาง วิศวกรอยากรู้ว่าในทุกช่วง K มิลลิวินาทีติดกัน สะพานแกว่งกว้างแค่ไหน ความกว้างของการแกว่งในช่วงหนึ่งคือค่ามากสุดลบด้วยค่าน้อยสุดในช่วงนั้น

ให้หาความกว้างของการแกว่งของทุกช่วง ตั้งแต่ช่วงที่เริ่มที่ค่าแรก ไปจนถึงช่วงที่จบที่ค่าสุดท้าย รวม N - K + 1 ช่วง

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ K คั่นด้วยช่องว่าง โดยที่ 1 ≤ K ≤ N ≤ 1000000

บรรทัดที่สองมีจำนวนเต็ม N ตัวคั่นด้วยช่องว่าง แต่ละตัวมีค่าตั้งแต่ -2000000000 ถึง 2000000000

ข้อมูลออก

บรรทัดเดียว มีจำนวนเต็ม N - K + 1 ตัวคั่นด้วยช่องว่างหนึ่งช่อง ตัวที่ i คือความกว้างของการแกว่งในช่วงที่เริ่มที่ค่าที่ i

8 3
5 -2 7 7 1 -6 3 2

9 9 6 13 9 9

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> value(n);
    for (int i = 0; i < n; i++) {
        cin >> value[i];
    }
    deque<int> high, low;
    for (int i = 0; i < n; i++) {
        while (!high.empty() && value[high.back()] <= value[i]) {
            high.pop_back();
        }
        high.push_back(i);
        while (!low.empty() && value[low.back()] >= value[i]) {
            low.pop_back();
        }
        low.push_back(i);
        if (high.front() <= i - k) {
            high.pop_front();
        }
        if (low.front() <= i - k) {
            low.pop_front();
        }
        if (i >= k - 1) {
            long long swing = (long long)value[high.front()] - value[low.front()];
            cout << swing << (i + 1 < n ? ' ' : '\n');
        }
    }
    return 0;
}

ข้อ 10 ภาพวาดบนรั้วไม้

ระดับยาก เวลาไม่เกิน 1 วินาที

รั้วข้างโรงเรียนทำจากแผ่นไม้ N แผ่นเรียงชิดกันเป็นแถว ทุกแผ่นกว้าง 1 เมตรและตั้งอยู่บนพื้นระดับเดียวกัน แผ่นที่ i สูง h_i เมตร ชมรมศิลปะอยากวาดภาพสี่เหลี่ยมผืนผ้าหนึ่งภาพบนรั้วให้ใหญ่ที่สุด ภาพต้องมีขอบล่างอยู่ที่พื้น ขอบซ้ายและขวาอยู่ตรงรอยต่อระหว่างแผ่นไม้หรือที่ปลายรั้ว และทุกส่วนของภาพต้องอยู่บนแผ่นไม้ ภาพจึงสูงได้ไม่เกินแผ่นที่เตี้ยที่สุดที่ภาพทับอยู่

ให้หาพื้นที่มากที่สุดของภาพเป็นตารางเมตร

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N โดยที่ 1 ≤ N ≤ 1000000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ h₁ ถึง h_N คั่นด้วยช่องว่าง โดยที่ 1 ≤ h_i ≤ 1000000000

ข้อมูลออก

พื้นที่มากที่สุดของภาพ

7
3 1 4 4 6 2 5

12

1
1000000000

1000000000

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> height(n);
    for (int i = 0; i < n; i++) {
        cin >> height[i];
    }
    vector<int> left_lower(n), right_lower(n);
    stack<int> boards;
    for (int i = 0; i < n; i++) {
        while (!boards.empty() && height[boards.top()] >= height[i]) {
            boards.pop();
        }
        if (boards.empty()) {
            left_lower[i] = -1;
        } else {
            left_lower[i] = boards.top();
        }
        boards.push(i);
    }
    while (!boards.empty()) {
        boards.pop();
    }
    for (int i = n - 1; i >= 0; i--) {
        while (!boards.empty() && height[boards.top()] >= height[i]) {
            boards.pop();
        }
        if (boards.empty()) {
            right_lower[i] = n;
        } else {
            right_lower[i] = boards.top();
        }
        boards.push(i);
    }
    long long best = 0;
    for (int i = 0; i < n; i++) {
        long long width = right_lower[i] - left_lower[i] - 1;
        best = max(best, width * height[i]);
    }
    cout << best << '\n';
    return 0;
}