HDU 4505 電梯裡的愛情：模擬調度與時間計算完整解析

題目背景

電梯初始在第 0 層，上一層 6 秒，下一層 4 秒，開門 5 秒（有人下才開），每人下電梯 1 秒。已知乘客目標樓層，電梯必須最終回到 0 層。求總耗時。
C ≤ 100, N ≤ 15, 樓層 ≤ 100。

核心觀察：樓層獨立性

電梯必須到達 最高目標樓層 Max，中途有乘客的樓層必停、無乘客不停。
總時間 = 上行 + 下行 + 停靠開關門 + 乘客下梯。

• 上行：Max * 6
• 下行：Max * 4
• 往返基礎：Max * 10
• 每個有乘客的樓層：開門 5 秒 + 每人 1 秒

算法流程

1. 統計每層乘客數 cnt[floor]，記錄最高層 Max
2. 基礎時間 ans = Max * 10
3. 遍歷 1..Max，若 cnt[i] > 0 則 ans += 5 + cnt[i]
4. 輸出 ans

完整 C 代碼

#include <stdio.h>
#include <string.h>

int main() {
    int C;
    scanf("%d", &C);
    while (C--) {
        int N;
        scanf("%d", &N);
        int cnt[101] = {0};
        int Max = 0;
        for (int i = 0; i < N; i++) {
            int floor;
            scanf("%d", &floor);
            cnt[floor]++;
            if (floor > Max) Max = floor;
        }

        int ans = Max * 10;               // 上去下來基礎時間
        for (int i = 1; i <= Max; i++) {
            if (cnt[i] > 0)
                ans += 5 + cnt[i];        // 開門 5s + 每人 1s
        }
        printf("%d\n", ans);
    }
    return 0;
}

樣例走算

輸入：
2
4 2 4 3 2
3 10 10 10

Case 1: 樓層 2(2人), 3(1人), 4(1人), Max=4
基礎 = 4*10 = 40
停靠: 2樓 5+2=7, 3樓 5+1=6, 4樓 5+1=6 → 總計 19
答案 = 40+19 = 59 ✓

Case 2: 10樓 3人, Max=10
基礎 = 10*10 = 100
停靠: 10樓 5+3=8
答案 = 108 ✓

常見誤區與邊界

複雜度

• 時間：O(C × (N + Max)) ≤ 100 × (15 + 100) ≈ 10⁴
• 空間：O(101) 計數數組

總結

本題看似模擬，實為 「最高層決定行程骨架，中間層獨立貢獻停靠時間」 的數學結構。關鍵在於識別「電梯必須到達最高層且不回頭」這一約束，將問題簡化為統計計數。這類「模擬題找規律化歸數學」是 ACM 入門必練思維。