Untitled

mail@pastecode.io avatar
unknown
plain_text
12 days ago
2.5 kB
4
Indexable
Never
#include <iostream>

using namespace std;

// Hàm để tính tổng khoảng cách di chuyển của hành khách từ một cửa
int calculateDistance(int N, int startPos, int numPassengers, bool seats[]) {
    int totalDistance = 0;
    for (int i = 0; i < numPassengers; ++i) {
        int distance = 0;
        while (true) {
            // Kiểm tra vị trí ngồi tại startPos
            if (startPos + distance < N && !seats[startPos + distance]) {
                totalDistance += distance + 1;
                seats[startPos + distance] = true;
                break;
            }
            if (startPos - distance >= 0 && !seats[startPos - distance]) {
                totalDistance += distance + 1;
                seats[startPos - distance] = true;
                break;
            }
            distance++;
        }
    }
    return totalDistance;
}

// Hàm để tìm tất cả các hoán vị của mảng
bool nextPermutation(int arr[], int size) {
    int i = size - 2;
    while (i >= 0 && arr[i] >= arr[i + 1]) {
        i--;
    }
    if (i < 0) return false;
    int j = size - 1;
    while (arr[j] <= arr[i]) {
        j--;
    }
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    for (int k = i + 1, l = size - 1; k < l; k++, l--) {
        temp = arr[k];
        arr[k] = arr[l];
        arr[l] = temp;
    }
    return true;
}

int main() {
    int T;
    cin >> T;
    
    for (int caseNum = 1; caseNum <= T; ++caseNum) {
        int N;
        cin >> N;
        
        int positions[3], passengers[3];
        for (int i = 0; i < 3; ++i) {
            cin >> positions[i] >> passengers[i];
            positions[i]--; // Để vị trí bắt đầu từ 0
        }
        
        int minDistance = 999999; // Giá trị lớn ban đầu
        int order[3] = {0, 1, 2};
        
        // Duyệt tất cả các thứ tự mở cửa
        do {
            bool seats[60] = {false}; // Mảng trạng thái ghế trống
            
            int currentDistance = 0;
            for (int i = 0; i < 3; ++i) {
                currentDistance += calculateDistance(N, positions[order[i]], passengers[order[i]], seats);
            }
            
            if (currentDistance < minDistance) {
                minDistance = currentDistance;
            }
        } while (nextPermutation(order, 3));
        
        cout << "Case #" << caseNum << "\n" << minDistance << "\n";
    }
    
    return 0;
}
Leave a Comment