Editorial for elevator: Thang máy

Hiểu bài toán

Bài toán mô phỏng quá trình vận chuyển N người lên các tầng khác nhau bằng một thang máy có sức chứa K người. Thang máy bắt đầu ở tầng 1 và phải quay về tầng 1 sau khi đã đưa tất cả mọi người lên tầng mong muốn. Chi phí (thời gian) di chuyển là khoảng cách giữa các tầng. Cần tìm tổng thời gian tối thiểu.

Quy luật hoạt động: Thang máy nên chở tối đa K người (trừ lượt cuối cùng) và đi thẳng đến tầng cao nhất trong số那些 người đó, sau đó quay lại tầng 1. Lặp lại cho đến khi hết người.

Nếu ta sắp xếp các tầng cần đến theo thứ tự giảm dần (từ cao xuống thấp), và chia thành các nhóm mỗi nhóm K người, thì tổng quãng đường sẽ là tổng khoảng cách từ tầng 1 lên tầng cao nhất của mỗi nhóm rồi quay về (nhân đôi khoảng cách).

Các cách tiếp cận

Cách Brute Force Simulation (Bubble Sort) - Phân tích từ Solution 2

#include <stdio.h>
#include <math.h>

int main() {
    int n, k;
    scanf("%d %d", &n, &k);
    int a[n];
    // Đọc dữ liệu
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    // Sắp xếp tăng dần (Bubble Sort)
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                int tmp = a[j];
                a[j] = a[j + 1];
                a[j + 1] = tmp;
            }
        }
    }

    int res = 0;
    // Duyệt từ người ở tầng cao nhất trở về (đi từ cuối mảng)
    // Vòng lặp while này xử lý các nhóm đầy đủ K người
    int current = n - 1;
    while (current >= 0) {
        // Thêm chi phí cho người xa nhất trong nhóm (tầng a[current])
        res += 2 * (a[current] - 1);
        current -= k; // Nhảy lùi K người
    }

    printf("%d", res);
    return 0;
}

• Time Complexity: O(N^2) do Bubble Sort (hoặc O(N log N) nếu dùng qsort)
• Space Complexity: O(N)

Cách tiếp cận này mô phỏng trực tiếp logic nhóm.

1. Sắp xếp mảng a tăng dần. Điều này giúp các tầng cao nhất nằm ở cuối mảng.
2. Duyệt từ phần tử cuối cùng (tầng cao nhất) về đầu.
3. Với mỗi người ở vị trí i, ta coi đây là người xa nhất trong nhóm K người hiện tại (bao gồm cả người này và K-1 người đứng sau).
4. Thêm 2 * (a[i] - 1) vào kết quả (đi lên tầng a[i], rồi về 1).
5. Nhảy lùi K bước để xử lý nhóm tiếp theo. Ví dụ: [2, 3, 4] với K=2. Sắp xếp: [2, 3, 4]. Duyệt:

• i=2 (tầng 4): Thêm 2*(4-1)=6. Nhảy về i=0.
• i=0 (tầng 2): Thêm 2*(2-1)=2. Nhảy về i=-2. Tổng = 8.

Cách Sort and Group (Optimized) - Phân tích từ Solution 1

#include <stdio.h>
#include <stdlib.h>

int a[2005]; // N <= 2000

// Hàm so sánh cho qsort, sort giảm dần
int cmp(const void *a, const void *b) {
    return (*(int *)b - *(int *)a);
}

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    // Sắp xếp giảm dần
    qsort(a, n, sizeof(int), cmp);

    long long sum = 0;
    // Duyệt từ đầu mảng (tầng cao nhất) mỗi nhóm K người
    for (int i = 0; i < n; i += k) {
        sum += (long long)(a[i] - 1) * 2;
    }

    printf("%ld", sum);
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Đây là phiên bản tối ưu hơn của cách tiếp cận 1.

1. Sử dụng hàm qsort để sắp xếp mảng giảm dần.
2. Sau khi sắp xếp, mảng trông như: [4, 3, 2] (ví dụ).
3. Vòng lặp for (int i = 0; i < n; i += k) sẽ duyệt qua các chỉ số 0, k, 2k....
4. Tại mỗi chỉ số i, a[i] chính là người ở tầng cao nhất của nhóm K người bắt đầu từ i.
5. Do đã sort giảm dần, ta chỉ cần lấy a[i] cho mỗi nhóm, cộng dồn (a[i] - 1) * 2 vào tổng. Ví dụ: [4, 3, 2] với K=2:

• i=0: a[0]=4 -> 2*(4-1)=6.
• i=2: a[2]=2 -> 2*(2-1)=2. Tổng = 8.

Cách Dynamic Programming (Tối ưu hóa quy hoạch động)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int N, K;
int p[2005];
int memo[2005];

int solve(int idx) {
    if (idx >= N) return 0;
    if (memo[idx] != -1) return memo[idx];

    int res = 2 * (p[idx] - 1) + solve(idx + 1);
    if (idx + K < N) {
        res = min(res, 2 * (p[idx] - 1) + solve(idx + K));
    }

    return memo[idx] = res;
}

int main() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> p[i];
    sort(p, p + N, greater<int>());

    memset(memo, -1, sizeof(memo));
    cout << solve(0) << endl;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là cách tiếp cận tổng quát hơn, phù hợp nếu quy tắc tính toán phức tạp hơn (ví dụ: chi phí khác nhau). Gọi dp[i] là chi phí tối thiểu để vận chuyển những người từ chỉ số i đến N-1. Công thức truy hồi: dp[i] = 2 * (p[i] - 1) + dp[i+1] Hoặc nếu ta quyết định cho thêm K-1 người vào thang máy cùng lúc (điều kiện i+K < N): dp[i] = 2 * (p[i] - 1) + dp[i+K] Tuy nhiên, trong bài toán này, vì chi phí chỉ phụ thuộc vào người xa nhất, giải pháp Greedy (các cách trên) là tối ưu nhất. DP ở đây chỉ để minh họa tính chất quy hoạch động.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Thứ tự phục vụ không ảnh hưởng đến tổng thời gian nếu thang máy luôn chở tối đa K người và đi thẳng lên tầng cao nhất rồi về (Greedy).
• Bài toán quy về việc chia N người thành các nhóm (khoảng N/K nhóm), mỗi nhóm có một 'đại diện' là người ở tầng cao nhất. Tổng thời gian là tổng khoảng cách của các đại diện này.
• Cần sắp xếp lại danh sách mong muốn để dễ dàng xác định người ở tầng cao nhất trong mỗi nhóm.

Lỗi thường gặp

• Sai sót trong việc sắp xếp (tăng dần/giảm dần) dẫn đến chọn sai người làm đại diện cho nhóm.
• Quên nhân đôi quãng đường (vì thang máy phải quay về tầng 1).
• Lỗi tràn số nguyên nếu dùng biến int cho tổng thời gian.