18.5 ลดความซับซ้อนและสองตัวชี้

สี่หน้าที่ผ่านมาสอนให้ดูว่าวิธีไหนช้า หน้านี้ลงมือทำให้เร็วขึ้น โจทย์เดียวกันจะถูกแก้สามรอบ จาก O(N³) เป็น O(N²) แล้วเป็น O(N) โดยแต่ละรอบตัดงานที่ทำซ้ำทิ้ง แล้ววัดเวลาจริงให้เห็นว่าต่างกันแค่ไหน ปิดท้ายด้วยเทคนิค สองตัวชี้ (two pointers) ซึ่งเปลี่ยนการไล่ทุกช่วง O(N²) ให้เหลือ O(N) ในโจทย์อีกกลุ่มหนึ่ง

โจทย์ ช่วงที่กำไรมากที่สุด

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

ถ้ากำไรเป็น -2 6 -1 4 -8 3 2 -5 ช่วง 6 -1 4 ได้ 9 มากที่สุด สังเกตว่าช่วงที่ดีที่สุดยอมรวมวันที่ขาดทุน 1 ไว้ด้วย เพราะวันถัดไปได้กลับมา 4

วิธีที่ 1 ลองทุกช่วง บวกใหม่ทุกครั้ง

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> profit(n);
    for (int i = 0; i < n; i++) {
        cin >> profit[i];
    }
    long long best = profit[0];
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            long long total = 0;
            for (int k = l; k <= r; k++) {
                total += profit[k];
            }
            best = max(best, total);
        }
    }
    cout << best << '\n';
    return 0;
}

8
-2 6 -1 4 -8 3 2 -5

9

l คือวันแรกของช่วง r คือวันสุดท้าย แล้ววนอีกชั้นบวกตั้งแต่ l ถึง r ลูปสามชั้นที่ทุกชั้นขึ้นกับ N เป็น O(N³) best เริ่มที่ profit[0] ไม่ใช่ 0 เพราะถ้าขาดทุนทุกวัน คำตอบต้องติดลบ ห้ามตอบ 0 ซึ่งหมายถึงไม่เลือกวันไหนเลย

วิธีที่ 2 ต่อยอดผลรวมเดิม

ดูลูปในสุดของวิธีที่ 1 ตอน r = 5 บวกวันที่ l ถึง 5 พอ r = 6 ก็บวกวันที่ l ถึง 5 ซ้ำอีกรอบ แล้วค่อยบวกวันที่ 6 เพิ่ม ทั้งที่ผลรวมถึงวันที่ 5 เพิ่งคำนวณเสร็จ ถ้าเก็บผลรวมไว้แล้วบวกแค่วันใหม่ ลูปในสุดก็หายไป

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> profit(n);
    for (int i = 0; i < n; i++) {
        cin >> profit[i];
    }
    long long best = profit[0];
    for (int l = 0; l < n; l++) {
        long long total = 0;
        for (int r = l; r < n; r++) {
            total += profit[r];
            best = max(best, total);
        }
    }
    cout << best << '\n';
    return 0;
}

8
-2 6 -1 4 -8 3 2 -5

9

total ย้ายมาอยู่นอกลูป r และเริ่มเป็น 0 ใหม่ทุกครั้งที่ l เปลี่ยน ทุกรอบของ r ทำงานแค่บวกหนึ่งครั้งกับเทียบหนึ่งครั้ง เหลือลูปสองชั้นเป็น O(N²)

วิธีที่ 3 ใช้ผลรวมสะสม

ให้ P[i] คือผลรวมของ i วันแรกแบบหน้า 5.4 โดย P[0] = 0 ผลรวมของวันที่ l ถึง r (นับช่องจาก 0) คือ P[r + 1] − P[l] ถ้าตรึง r ไว้ อยากให้ผลลบนี้มากที่สุด ก็ต้องเลือก P[l] ที่ น้อยที่สุด ในบรรดา P[0] ถึง P[r] ไม่ต้องลองทุก l เลย แค่จำค่าน้อยสุดที่เคยเห็นมาไว้ในตัวแปรเดียว แล้วอัปเดตไปพร้อมกับ r

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> profit(n);
    for (int i = 0; i < n; i++) {
        cin >> profit[i];
    }
    long long best = profit[0];
    long long prefix = 0, lowest = 0; // (1)!
    for (int r = 0; r < n; r++) {
        prefix += profit[r]; // (2)!
        best = max(best, prefix - lowest); // (3)!
        lowest = min(lowest, prefix); // (4)!
    }
    cout << best << '\n';
    return 0;
}

1. prefix คือ P ของวันปัจจุบัน lowest คือ P ที่น้อยที่สุดที่เคยเห็น เริ่มที่ P[0] = 0
2. ตอนนี้ prefix เป็น P[r + 1]
3. ช่วงที่ดีที่สุดที่จบวันที่ r มีผลรวม P[r + 1] ลบ P ที่น้อยที่สุดก่อนหน้า
4. อัปเดตทีหลังบรรทัดก่อนหน้า เพื่อไม่ให้ลบตัวเองจนได้ช่วงที่ว่างเปล่า

8
-2 6 -1 4 -8 3 2 -5

9

ที่ r = 3 ได้ 7 − (−2) = 9 คือช่วงวันที่ 1 ถึง 3 (นับช่องจาก 0) ซึ่งก็คือ 6 -1 4 ลูปเดียวทำงาน O(1) ต่อรอบ รวมเป็น O(N) และไม่ต้องมีอาเรย์ P ด้วย ใช้แค่สองตัวแปร

เร็วขึ้นแค่ไหน

วัดด้วยวิธีเดียวกับหน้า 18.2 สร้างกำไรสุ่มตั้งแต่ −1000 ถึง 1000 ด้วย rand() จับเวลาเฉพาะส่วนที่คำนวณ ลูปเหมือนสามโปรแกรมข้างบนทุกบรรทัด เครื่องเดิม -O2 ค่ากลางของ 5 ครั้ง ช่องที่บอกว่าไม่ได้รันคือรอนานเกินไป

ถ้าประมาณช่องที่ไม่ได้รันจากรูปร่าง วิธีที่ 1 ที่ N = 100,000 ใช้ราว 64 × 1000 วินาที หรือเกือบ 18 ชั่วโมง วิธีที่ 2 ที่ N = 1,000,000 ใช้ราว 3.7 × 100 วินาที หรือราว 6 นาที ส่วนวิธีที่ 3 ที่ N สิบล้านยังใช้แค่หนึ่งในร้อยวินาที โจทย์ที่ให้ N ≤ 3000 ใช้วิธีที่ 2 ได้ ส่วน N ≤ 10⁵ ขึ้นไปต้องวิธีที่ 3 ตรงกับตารางขอบเขตในหน้า 18.2

สองตัวชี้

อีกโจทย์หนึ่ง ร้านขนม N ร้านเรียงกันบนถนน ร้านที่ i ขายขนมชิ้นละ c_i บาท ทุกราคาเป็นจำนวนเต็มบวก น้องมีเงิน S บาท อยากเดินซื้อร้านละหนึ่งชิ้นจากร้านที่อยู่ติดกันหนึ่งช่วง ซื้อได้มากที่สุดกี่ร้าน หรือก็คือหาช่วงที่ยาวที่สุดที่ผลรวมไม่เกิน S

วิธีตรงไปตรงมาคือลองทุกจุดเริ่ม l แล้วขยาย r ไปจนเงินไม่พอ

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long budget;
    cin >> n >> budget;
    vector<int> cost(n);
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    int best = 0;
    for (int l = 0; l < n; l++) {
        long long total = 0;
        for (int r = l; r < n; r++) {
            total += cost[r];
            if (total > budget) {
                break;
            }
            best = max(best, r - l + 1);
        }
    }
    cout << best << '\n';
    return 0;
}

8 12
4 2 7 1 3 5 2 6

4

มี break ก็จริง แต่ถ้า S ใหญ่จนช่วงยาวเป็นครึ่งหนึ่งของถนน แต่ละ l ต้องขยายไปราว N/2 ร้าน กรณีแย่ที่สุดยังเป็น O(N²)

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

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long budget;
    cin >> n >> budget;
    vector<int> cost(n);
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    int best = 0;
    long long total = 0;
    int l = 0;
    for (int r = 0; r < n; r++) {
        total += cost[r];
        while (total > budget) {
            total -= cost[l];
            l++;
        }
        best = max(best, r - l + 1);
    }
    cout << best << '\n';
    return 0;
}

8 12
4 2 7 1 3 5 2 6

4

มี while ซ้อนอยู่ใน for ดูเหมือน O(N²) แต่ให้นับว่า l++ ทำได้กี่ครั้ง l เริ่มที่ 0 เพิ่มทีละหนึ่ง ไม่เคยลดลง และไม่เกิน N ทั้งโปรแกรมจึงเลื่อน l รวมกันไม่เกิน N ครั้ง ส่วน r เลื่อน N ครั้ง งานรวมไม่เกิน 2N เป็น O(N) การนับแบบนี้คือดูว่าตัวแปรเดินไปได้ไกลแค่ไหนตลอดทั้งโปรแกรม แทนที่จะคูณรอบของลูปนอกกับลูปใน

วัดแบบเดียวกับตารางข้างบน ราคาสุ่ม 1 ถึง 100 บาท S = 25N ทำให้ช่วงที่ดีที่สุดยาวราวครึ่งหนึ่งของ N

สองตัวชี้ใช้ได้เมื่อมีสมบัติว่า ถ้าช่วงหนึ่งใช้ได้ ช่วงที่อยู่ข้างในก็ใช้ได้ด้วย เช่น ผลรวมไม่เกิน S เมื่อทุกค่าเป็นบวก หรือไม่มีค่าซ้ำในช่วง ถ้าไม่มีสมบัตินี้ วิธีนี้ให้คำตอบผิด ดูได้ในส่วนลองทำให้พัง

ลองทำให้พัง

สองตัวชี้กับค่าติดลบ

ถ้าบางร้านมีโปรโมชันคืนเงิน ราคาติดลบได้ ลองป้อนข้อมูลนี้ให้โปรแกรม window-two โดยไม่แก้อะไร

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long budget;
    cin >> n >> budget;
    vector<int> cost(n);
    for (int i = 0; i < n; i++) {
        cin >> cost[i];
    }
    int best = 0;
    long long total = 0;
    int l = 0;
    for (int r = 0; r < n; r++) {
        total += cost[r];
        while (total > budget) {
            total -= cost[l];
            l++;
        }
        best = max(best, r - l + 1);
    }
    cout << best << '\n';
    return 0;
}

4 3
2 5 -6 2

2

คำตอบที่ถูกคือ 4 เพราะซื้อครบทั้งสี่ร้านใช้เงิน 2 + 5 − 6 + 2 = 3 บาทพอดี แต่โปรแกรมตอบ 2 ตอน r = 1 ผลรวม 7 เกิน 3 ลูป while จึงทิ้งร้าน 0 และร้าน 1 ไปถาวร ทั้งที่ร้าน 2 จะคืนเงิน 6 บาทในรอบถัดไป ข้อสังเกตที่ว่าจุดเริ่มไม่มีวันถอยไม่จริงอีกแล้วเมื่อมีค่าติดลบ ไม่มี error ไม่มี warning ชุดทดสอบที่มีแต่ค่าบวกก็ผ่านหมด ก่อนใช้สองตัวชี้ต้องตรวจขอบเขตของค่าในโจทย์ทุกครั้ง ถ้าโจทย์มีค่าติดลบ ต้องใช้วิธีอื่นที่ซับซ้อนกว่านี้

สรุป

• ลดความซับซ้อนด้วยการตัดงานที่ทำซ้ำ เก็บผลรวมไว้ต่อยอดลด O(N³) เป็น O(N²) จำค่าที่ดีที่สุดไว้ลด O(N²) เป็น O(N)
• ช่วงกำไรสูงสุดใช้ผลรวมสะสมลบค่าน้อยสุดที่เคยเห็น ทำได้ใน O(N) N สิบล้านใช้ 0.010 วินาทีบนเครื่องที่เขียนเอกสารนี้
• สองตัวชี้ใช้กับโจทย์หาช่วงที่ ถ้าช่วงใช้ได้ ช่วงข้างในก็ใช้ได้ ตัวชี้ทั้งสองเดินไปทางเดียว รวมไม่เกิน 2N ก้าว
• นับความซับซ้อนของ while ในสองตัวชี้ ให้นับว่าตัวแปรเดินได้ไกลแค่ไหนทั้งโปรแกรม ไม่ใช่คูณรอบลูป
• ค่าติดลบทำให้สองตัวชี้แบบผลรวมผิด ตรวจขอบเขตของค่าก่อนใช้

กลับไปเช็กรายการ ผ่านบทนี้เมื่อ แล้วไปทำแบบฝึกหัด