EasyRating 1404
1700. Number of Students Unable to Eat Lunch
arraystackqueuesimulation
解題說明
Number of Students Unable to Eat Lunch
題目描述:有一排學生和一疊三明治。每個學生偏好圓形(0)或方形(1)三明治。學生排成佇列,若隊首學生喜歡棧頂三明治就拿走,否則移到隊尾。當沒有學生願意拿棧頂三明治時停止。求最終無法吃到午餐的學生數。
解題思路:關鍵觀察是學生的順序不重要,只要佇列中還有偏好當前棧頂類型的學生,該三明治就會被拿走。因此只需統計偏好 0 和 1 的學生數,然後依序遍歷三明治:若當前三明治類型的計數大於 0 就減一,否則剩餘所有學生都吃不到。
C++ 解法
複雜度分析
時間複雜度:O(n) — 遍歷學生和三明治各一次。
空間複雜度:O(1) — 只需兩個計數器。
虛擬碼
1. Count number of students preferring 0 and 1
2. For each sandwich (top to bottom):
a. If count of students preferring this type is 0:
- Return total remaining students (count[0] + count[1])
b. Else decrement that count
3. Return 0 (all students fed)其他解法
模擬法:直接模擬佇列過程,用 queue 存學生、用 stack 存三明治。當一整輪沒有任何學生拿到三明治時停止。時間最壞 O(n^2),直觀但效率低。
計數 + 提前終止:與最佳解類似,但用 while 迴圈追蹤連續被跳過的學生數,達到佇列長度時停止。邏輯等價但更接近原始模擬的描述。
延伸思考
- 若三明治有超過兩種類型(例如 k 種),演算法如何推廣?
- 若每個學生有一個偏好列表(可以接受多種類型),如何處理?
- 若要最小化無法吃到午餐的學生數,可以重新排列三明治順序嗎?