programming.in.th · ข้อ 2035

GARAGE โรงจอดรถ: ตอนมีรถรอคิว ช่องที่เพิ่งว่างคือช่องว่างช่องเดียว

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

★☆☆☆☆ simulationพื้นฐาน อ่าน 9 นาที 11 กันยายน 2026

โจทย์ · เก็บค่าจอดรถทั้งวัน

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

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

อินพุต / ขอบเขต / เอาต์พุต

อินพุต: บรรทัดแรกคือ N กับ M ต่อด้วย N บรรทัด บรรทัดที่ s คือราคาของช่อง s ต่อด้วย M บรรทัด บรรทัดที่ k คือน้ำหนักของรถคัน k แล้วปิดด้วย 2M บรรทัดเรียงตามเวลา เลขบวก i คือรถคัน i มาถึง เลขลบ -i คือรถคัน i ออก
รับประกัน: รถทุกคันโผล่สองครั้งพอดี มาก่อนแล้วค่อยออก และไม่มีคันไหนออกไปทั้งที่ยังรอคิวอยู่
ขอบเขต: 1 ≤ N ≤ 100, 1 ≤ M ≤ 2,000, ราคาแต่ละช่อง 1 ถึง 100 และน้ำหนักรถ 1 ถึง 10,000 กิโลกรัม เวลา 1 วินาที หน่วยความจำ 64 เมกะไบต์
เอาต์พุต: รายได้รวมทั้งวันเป็นดอลลาร์ หนึ่งจำนวน
ให้คะแนน: ชุดทดสอบมูลค่า 40 คะแนนรับประกันว่ารถทุกคันที่มาถึงมีช่องว่างรออยู่ คือไม่มีใครต้องรอเลย

EXAMPLE
Input	Output
3 4 2 3 5 200 100 300 800 3 2 -3 1 4 -4 -2 -1	5300

อ่านตัวอย่างนี้ยังไง

บรรทัดแรกบอกว่ามี 3 ช่อง รถ 4 คัน อีก 3 บรรทัดถัดมาคือราคาช่อง 1 ถึง 3 (2, 3, 5) อีก 4 บรรทัดคือน้ำหนักรถคัน 1 ถึง 4 (200, 100, 300, 800) ที่เหลือ 8 บรรทัดคือเหตุการณ์ตามเวลา ระวังว่าเลขในส่วนนี้คือเลขประจำรถ ไม่ใช่เลขช่อง บรรทัดแรกของส่วนนี้เป็น 3 จึงแปลว่ารถคัน 3 มาถึงเป็นคันแรก ไม่ใช่รถคันแรกไปจอดช่อง 3

คำตอบมีหน่วยเป็นดอลลาร์ และนับเฉพาะตอนรถได้จอด ในตัวอย่างนี้ได้จอด 4 ครั้ง คือ คัน 3 ช่อง 1 ได้ 300 คูณ 2 เท่ากับ 600 คัน 2 ช่อง 2 ได้ 100 คูณ 3 เท่ากับ 300 คัน 1 ช่อง 1 ได้ 200 คูณ 2 เท่ากับ 400 คัน 4 ช่อง 3 ได้ 800 คูณ 5 เท่ากับ 4,000 รวมเป็น 5,300 สังเกตว่ารถคัน 1 ได้ช่อง 1 ซึ่งถูกที่สุด เพราะคัน 3 เพิ่งออกไปพอดี และไม่มีรถคันไหนต้องรอเลย ตัวอย่างนี้จึงอยู่ในชุด 40 คะแนน

เส้นเวลาของตัวอย่างในโจทย์ ช่องละหนึ่งแถว แถบหนึ่งแถบคือรถหนึ่งคันตั้งแต่ได้จอดจนออก ตัวเลขใต้ชื่อรถคือค่าจอดของมัน ช่อง 1 ถูกใช้สองรอบ เพราะคัน 3 ออกก่อนคัน 1 มาถึง รวมทุกแถบได้ 5,300

ใบ้

ขอบเขตเล็กมาก ช่องไม่เกิน 100 รถไม่เกิน 2,000 คัน ข้อนี้จึงไม่ได้วัดความเร็ว มันวัดว่าเราจำลองกติกาครบทุกกรณีไหม ส่วนที่ตัวอย่างในโจทย์ไม่ได้โชว์ให้ดูเลยคือวันที่รถล้น

ลองนึกภาพตอนที่มีรถรออยู่หน้าทางเข้า แล้วรถคันหนึ่งขับออก ตอนนั้นโรงจอดมีช่องว่างกี่ช่อง และคุณต้องค้นหาช่องให้หัวคิวจริงหรือเปล่า

ลองเอง · เป็นคนเฝ้าโรงจอดหนึ่งวัน

วันนี้ไม่มีใครต้องรอเลย ลองจัดให้ถูกทุกคันก่อน แล้วดูว่ารายได้ออกมา 5,300 ไหม

กดช่องที่รถคันนี้ควรได้จอด หรือกดปุ่มด้านล่างถ้ามันต้องรอหรือกำลังจะออก

รายได้ 0 ดอลลาร์

เงินเก็บตอนรถได้จอด คือน้ำหนักคูณราคาของช่องนั้น ไม่ได้เก็บตอนรถออก

ลองให้ครบทั้งสามวันก่อนนะครับ โดยเฉพาะวันที่รถล้น ช่วงที่มีรถออกตอนคิวยังไม่ว่าง คือช่วงที่เฉลยข้างล่างพูดถึง

เฉลย ตอนที่ 1 · ตอนมีคนรอ ช่องที่เพิ่งว่างคือช่องว่างช่องเดียว

ที่มาของแนวคิดนี้

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

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

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

ผลคือตอนรถออก เราไม่ต้องหาอะไรเลย ปล่อยช่องคืน แล้วถ้ามีคิว ให้หัวคิวเข้าช่องเดิมนั้น งานค้นหาเหลือแค่ตอนรถมาถึง ซึ่งสแกนช่อง 1 ถึง N หาช่องแรกที่ว่าง

หัวใจของทั้งข้อ

// รถออก: ปล่อยช่องคืน แล้วถ้ามีคนรอ ให้หัวคิวเข้าช่องนี้เลย ไม่ต้องสแกนหา
int s = at[-x]; who[s] = 0;
if(!wait.empty()){ park(wait.front(), s); wait.pop(); }

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

เส้นเวลาของวันที่รถล้น สองช่อง สี่คัน คัน 2 กับ 4 มาถึงตอนเต็มจึงรอ (แถบเส้นประ) พอคัน 1 ออก ช่อง 2 เป็นช่องว่างช่องเดียว หัวคิวคือคัน 2 จึงได้ช่อง 2 พอคัน 3 ออก คัน 4 ได้ช่อง 1 ที่แพงที่สุดไปด้วยค่าจอด 10,000 รวมทั้งวัน 16,200

รูปนี้โชว์อีกอย่างที่คนมักพลาดตอนอ่านโจทย์ คือค่าจอดของคันที่รอคิวคิดจากช่องที่มันได้จริง คัน 4 ได้ช่อง 1 ที่แพงที่สุดเพราะจังหวะล้วน ๆ รถที่ออกเป็นคันที่สองของวันคือคัน 3 ซึ่งจอดช่อง 1 อยู่พอดี ถ้าสลับให้คัน 3 ออกก่อนคัน 1 หัวคิวคือคัน 2 จะได้ช่อง 1 ไปแทน คัน 4 เหลือช่อง 2 ค่าจอดของมันจะเหลือ 4,000 และรายได้ทั้งวันจะเหลือ 11,700

เดินวันที่รถล้นให้ดูทีละเหตุการณ์

ขั้น 0

2 ช่อง ราคา 5 และ 2 รถ 4 คัน หนัก 100, 500, 1,000, 2,000 กิโลกรัม

สถานะหลังแต่ละเหตุการณ์
เหตุการณ์	ช่อง 1	ช่อง 2	คิว	ได้เพิ่ม	รวม
คัน 3 มา	คัน 3	ว่าง	·	5,000	5,000
คัน 1 มา	คัน 3	คัน 1	·	200	5,200
คัน 2 มา	คัน 3	คัน 1	2	·	5,200
คัน 4 มา	คัน 3	คัน 1	2, 4	·	5,200
คัน 1 ออก	คัน 3	คัน 2	4	1,000	6,200
คัน 3 ออก	คัน 4	คัน 2	·	10,000	16,200
คัน 2 ออก	คัน 4	ว่าง	·	·	16,200
คัน 4 ออก	ว่าง	ว่าง	·	·	16,200

ยอดสุดท้าย 16,200 ตรงกับตัวตรวจที่ไล่จับคู่ใหม่หลังทุกเหตุการณ์ และทั้ง 4 ครั้งที่มีรถได้จอด ไม่มีครั้งไหนที่ต้องเลือกระหว่างช่องว่างหลายช่องพร้อมกับมีคนรอ

โค้ด

ดูโค้ดเต็ม (ได้ 100 คะแนน)

garage.cpp

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m; scanf("%d %d", &n, &m);
    vector<long long> rate(n + 1), w(m + 1);
    for(int s = 1; s <= n; s++) scanf("%lld", &rate[s]);
    for(int k = 1; k <= m; k++) scanf("%lld", &w[k]);
    vector<int> who(n + 1, 0);      // who[s] = รถที่จอดช่อง s อยู่ (0 = ว่าง)
    vector<int> at(m + 1, 0);       // at[k] = ช่องที่รถคัน k จอด
    queue<int> wait;                // รถที่รอหน้าทางเข้า เรียงตามลำดับที่มาถึง
    long long income = 0;
    auto park = [&](int car, int s){ who[s] = car; at[car] = s; income += w[car] * rate[s]; };
    for(int e = 0; e < 2 * m; e++){
        int x; scanf("%d", &x);
        if(x > 0){
            int s = 1; while(s <= n && who[s] != 0) s++;   // ช่องว่างเลขน้อยสุด
            if(s <= n) park(x, s);
            else wait.push(x);                             // เต็ม ต่อท้ายคิว
        } else {
            int s = at[-x]; who[s] = 0;
            // มีคนรอแปลว่าก่อนหน้านี้เต็มทุกช่อง ช่องที่เพิ่งว่างจึงเป็นช่องว่างช่องเดียว
            if(!wait.empty()){ park(wait.front(), s); wait.pop(); }
        }
    }
    printf("%lld\n", income);
}

รายได้สูงสุดที่เป็นไปได้คือ 2,000 คัน คูณราคา 100 คูณน้ำหนัก 10,000 ได้ 2,000,000,000 ซึ่งยังไม่เกินเพดานของ int ที่ 2,147,483,647 แต่เหลือที่ว่างอยู่นิดเดียว ผมจึงใช้ long long ไว้ก่อน ไม่ต้องมานั่งพิสูจน์ว่ารอด

ดูโค้ดชุด 40 คะแนน (ไม่มีรถรอ)

garage_40.cpp

// ชุดทดสอบ 40 คะแนน: รับประกันว่าไม่มีรถคันไหนต้องรอ จึงไม่ต้องมีคิวเลย
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m; scanf("%d %d", &n, &m);
    vector<long long> rate(n + 1), w(m + 1);
    for(int s = 1; s <= n; s++) scanf("%lld", &rate[s]);
    for(int k = 1; k <= m; k++) scanf("%lld", &w[k]);
    vector<int> who(n + 1, 0), at(m + 1, 0);
    long long income = 0;
    for(int e = 0; e < 2 * m; e++){
        int x; scanf("%d", &x);
        if(x > 0){
            int s = 1; while(who[s] != 0) s++;   // ชุดนี้รับประกันว่าเจอช่องว่างก่อนเลย n เสมอ
            who[s] = x; at[x] = s; income += w[x] * rate[s];
        } else who[at[-x]] = 0;
    }
    printf("%lld\n", income);
}

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

ดูตัวตรวจที่ใช้เทียบ

brute_garage.cpp

// ตัวตรวจ ไม่มีคิว และไม่ใช้ข้อสังเกตเรื่องช่องที่เพิ่งว่าง
// เก็บสถานะของรถทุกคันไว้เป็นตัวเลข แล้วหลังทุกเหตุการณ์ ไล่จับคู่ซ้ำจนนิ่ง
// คือรถที่รออยู่และมาถึงเร็วที่สุด ได้ช่องว่างที่เลขน้อยที่สุด
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, m; scanf("%d %d", &n, &m);
    vector<long long> rate(n + 1), w(m + 1);
    for(int s = 1; s <= n; s++) scanf("%lld", &rate[s]);
    for(int k = 1; k <= m; k++) scanf("%lld", &w[k]);
    vector<int> state(m + 1, -1);   // -1 ยังไม่มา, 0 รออยู่, s > 0 จอดช่อง s, -2 ออกไปแล้ว
    vector<int> came(m + 1, 0);     // ลำดับเหตุการณ์ที่รถคันนั้นมาถึง
    long long income = 0;
    for(int e = 0; e < 2 * m; e++){
        int x; scanf("%d", &x);
        if(x > 0){ state[x] = 0; came[x] = e; }
        else state[-x] = -2;
        while(true){
            int best = -1;
            for(int k = 1; k <= m; k++)
                if(state[k] == 0 && (best < 0 || came[k] < came[best])) best = k;
            int freeS = -1;
            for(int s = 1; s <= n && freeS < 0; s++){
                bool used = false;
                for(int k = 1; k <= m; k++) if(state[k] == s) used = true;
                if(!used) freeS = s;
            }
            if(best < 0 || freeS < 0) break;
            state[best] = freeS; income += w[best] * rate[freeS];
        }
    }
    printf("%lld\n", income);
}

ตัวตรวจไม่มีคิวและไม่เชื่อว่าช่องที่เพิ่งว่างเป็นช่องเดียว มันจับคู่ตามกติกาตรง ๆ ซ้ำจนไม่มีอะไรขยับ ผมสุ่มวันทำงานเล็ก ๆ (ไม่เกิน 5 ช่อง 8 คัน) 900 วัน ในนั้น 213 วันมีรถต้องรอ แล้วเทียบกับโค้ดเต็ม ตรงกันหมด ส่วนโค้ดชุด 40 คะแนนเทียบเฉพาะ 300 วันที่ไม่มีใครรอ ก็ตรงกันหมดเช่นกัน หน้าเว็บนี้รันด่านตรวจคล้ายกันตอนบิลด์อีก 500 วัน ซึ่งมีวันที่รถล้น 1 วัน

เวลาที่วัดได้บนเครื่องผม ชุดที่หนักที่สุดคือ 100 ช่อง รถ 2,000 คันที่มาถึงหมดก่อนแล้วค่อยทยอยออก ทำให้มีคนรอคิวยาวเกือบสองพันคัน โค้ดเต็มใช้เวลา 0.007 วินาที จากลิมิต 1 วินาที และตอบ 2,000,000,000 ตรงกับตัวตรวจ

ท่าที่ติดมือกลับไป

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

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

บิลค่าใช้จ่าย
ทาง	จำนวนครั้งที่ตรวจช่อง	เวลาชุดหนักสุด
ตัวตรวจ ไล่จับคู่ซ้ำหลังทุกเหตุการณ์	ไม่เกินราว 800,000,000 ครั้ง	0.24 วินาที
คิวหนึ่งอัน สแกนหาช่องว่างตอนรถมาถึง	ไม่เกิน 200,000 ครั้ง	0.007 วินาที

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

สรุปบรรทัดเดียว

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

แหล่งที่มา

โจทย์ GARAGE บน programming.in.th ข้อ 2035 programming.in.th/tasks/2035 (สืบค้น 11 กันยายน 2026)
ต้นฉบับจาก International Olympiad in Informatics ครั้งที่ 21 ปี 2009 วันที่สอง ตามที่ระบุไว้ท้ายโจทย์
ตัวอย่างวันที่รถล้นในหน้านี้ผมแต่งเพิ่มเอง เพราะตัวอย่างในโจทย์ภาษาไทยไม่มีรถรอเลย