Hướng dẫn cho Lập lịch sửa chửa ô tô

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Có \(n\) chiếc xe cần sửa chữa. Với mỗi chiếc xe \(i\):

\(A[i]\) là số tiền phạt phải trả cho mỗi ngày chậm trễ.
\(B[i]\) là số ngày cần thiết để hoàn thành việc sửa chữa.

Các xe được sửa chữa tuần tự (xong xe này mới đến xe khác). Nếu xe \(i\) hoàn thành vào cuối ngày \(T\), tiền phạt của xe đó là \(T \cdot A[i]\). Hãy tìm thứ tự sửa xe sao cho tổng tiền phạt của tất cả các xe là nhỏ nhất.

Phân tích

Điều kiện: \(n \leq 10000\), \(A[i] \leq 10000\), \(B[i] \leq 100\).
Nhận xét: Đây là một bài toán lập lịch (scheduling problem) điển hình. Quyết định sửa xe nào trước sẽ ảnh hưởng đến thời gian hoàn thành của tất cả các xe sửa sau đó.
Chiến thuật: Ta cần tìm một tiêu chí để sắp xếp thứ tự ưu tiên các xe. Giả sử ta có hai xe \(i\) và \(j\) đứng cạnh nhau trong lịch trình.
- Nếu sửa \(i\) trước \(j\):
  - Xe \(i\) xong tại thời điểm \(T + B[i]\), tiền phạt: \((T + B[i]) \cdot A[i]\).
  - Xe \(j\) xong tại thời điểm \(T + B[i] + B[j]\), tiền phạt: \((T + B[i] + B[j]) \cdot A[j]\).
  - Tổng tiền phạt của hai xe: \(P_{ij} = (T + B[i]) \cdot A[i] + (T + B[i] + B[j]) \cdot A[j]\).
- Nếu sửa \(j\) trước \(i\):
  - Tổng tiền phạt của hai xe: \(P_{ji} = (T + B[j]) \cdot A[j] + (T + B[j] + B[i]) \cdot A[i]\).
- Để chọn thứ tự tối ưu, ta so sánh \(P_{ij}\) và \(P_{ji}\). Sau khi triệt tiêu các hạng tử giống nhau, ta có:
  - \(P_{ij} < P_{ji} \Leftrightarrow B[i] \cdot A[j] < B[j] \cdot A[i] \Leftrightarrow \frac{A[i]}{B[i]} > \frac{A[j]}{B[j]}\).
Kết luận: Ta nên sắp xếp các xe theo thứ tự giảm dần của tỉ số \(\frac{A[i]}{B[i]}\).

Cách làm đơn giản (Brute Force)

Ý tưởng

Thử tất cả các hoán vị của \(n\) chiếc xe, tính tổng tiền phạt cho mỗi hoán vị và chọn hoán vị có tổng tiền phạt nhỏ nhất.

Độ phức tạp

Thời gian: \(O(n! \cdot n)\)
Đánh giá: Chỉ chạy được với \(n \leq 10\). Với \(n = 10000\), cách này không khả thi.

Code Brute Force

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> a(n), b(n), p(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 0; i < n; i++) p[i] = i;

    long long min_penalty = -1;
    vector<int> best_order;

    do {
        long long current_penalty = 0;
        long long current_time = 0;
        for (int i : p) {
            current_time += b[i];
            current_penalty += current_time * a[i];
        }
        if (min_penalty == -1 || current_penalty < min_penalty) {
            min_penalty = current_penalty;
            best_order = p;
        }
    } while (next_permutation(p.begin(), p.end()));

    cout << min_penalty << endl;
    for (int i : best_order) cout << i + 1 << " ";
}

Python

import itertools

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
p = list(range(n))

min_penalty = float('inf')
best_order = []

for perm in itertools.permutations(p):
    current_penalty = 0
    current_time = 0
    for i in perm:
        current_time += b[i]
        current_penalty += current_time * a[i]
    if current_penalty < min_penalty:
        min_penalty = current_penalty
        best_order = perm

print(min_penalty)
print(*(i + 1 for i in best_order))

Hướng giải quyết (Tối ưu)

Thuật toán

Lưu thông tin mỗi xe gồm: chỉ số (ID), \(A[i]\) và \(B[i]\).
Sắp xếp danh sách các xe theo tiêu chí: xe \(i\) đứng trước xe \(j\) nếu \(A[i] \cdot B[j] > A[j] \cdot B[i]\). (Sử dụng phép nhân thay vì phép chia để tránh sai số số thực).
Tính tổng tiền phạt dựa trên thứ tự đã sắp xếp:
- Duy trì biến currentTime tích lũy thời gian sửa xe.
- Với mỗi xe \(i\), penalty = penalty + currentTime * A[i].
In ra tổng tiền phạt và thứ tự các ID xe.

Lưu ý

Tổng tiền phạt có thể rất lớn (lên tới \(10^{14}\)), vì vậy trong C++ cần sử dụng kiểu dữ liệu long long.

Độ phức tạp

Thời gian: \(O(n \log n)\) do thao tác sắp xếp.
Bộ nhớ: \(O(n)\) để lưu trữ thông tin các xe.

Code tham khảo

C++

#include <bits/stdc++.h>
using namespace std;

struct Car {
    int id;
    int a, b;
};

bool compareCars(const Car& i, const Car& j) {
    // So sánh tỉ số a/b bằng cách nhân chéo: a[i]/b[i] > a[j]/b[j]
    return (long long)i.a * j.b > (long long)j.a * i.b;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<Car> cars(n);
    for (int i = 0; i < n; i++) {
        cars[i].id = i + 1;
        cin >> cars[i].a;
    }
    for (int i = 0; i < n; i++) {
        cin >> cars[i].b;
    }

    // Sắp xếp các xe theo chiến thuật tham lam
    sort(cars.begin(), cars.end(), compareCars);

    long long totalPenalty = 0;
    long long currentTime = 0;
    for (int i = 0; i < n; i++) {
        currentTime += cars[i].b;
        totalPenalty += currentTime * cars[i].a;
    }

    cout << totalPenalty << "\n";
    for (int i = 0; i < n; i++) {
        cout << cars[i].id << (i == n - 1 ? "" : " ");
    }

    return 0;
}

Python

import sys

def solve():
    # Đọc dữ liệu
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    n = int(input_data[0])
    a = list(map(int, input_data[1:n+1]))
    b = list(map(int, input_data[n+1:2*n+1]))

    # Tạo danh sách các xe với (id, a, b)
    cars = []
    for i in range(n):
        cars.append({
            'id': i + 1,
            'a': a[i],
            'b': b[i]
        })

    # Sắp xếp theo tỉ số a/b giảm dần
    # Sử dụng key là một giá trị đại diện cho tỉ số a/b
    # Hoặc sử dụng hàm so sánh tùy chỉnh (trong Python 3 dùng cmp_to_key)
    from functools import cmp_to_key
    def compare(car1, car2):
        val1 = car1['a'] * car2['b']
        val2 = car2['a'] * car1['b']
        if val1 > val2:
            return -1
        elif val1 < val2:
            return 1
        return 0

    cars.sort(key=cmp_to_key(compare))

    # Tính tổng tiền phạt
    total_penalty = 0
    current_time = 0
    order = []

    for car in cars:
        current_time += car['b']
        total_penalty += current_time * car['a']
        order.append(str(car['id']))

    # In kết quả
    print(total_penalty)
    print(" ".join(order))

if __name__ == "__main__":
    solve()

Bình luận

Tải bình luận...

Không có bình luận nào.