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 種），演算法如何推廣？
- 若每個學生有一個偏好列表（可以接受多種類型），如何處理？
- 若要最小化無法吃到午餐的學生數，可以重新排列三明治順序嗎？