let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

CAR - Lập lịch sửa chữa ô tô

solution.md

Đầu tiên xét các trường hợp đặc biệt như sau:

  • Giữa 2 xe có thời gian sửa chữa bằng nhau thì ta sẽ ưa tiên xe có tiền phạt cao hơn được sửa trước.
  • Giữa 2 xe có cùng tiền phạt thì ta sẽ ưu tiên xe có thời gian sửa nhanh hơn được sửa trước.

Từ đó có thể liên tưởng đến phương pháp tham lam như sau: Sắp các xe lại theo A/B giảm dần, rồi lần lượt sửa các xe theo đúng thứ tự đó.

Chứng minh tính đúng đắn của phương pháp:

Để chứng minh cách làm trên là đúng, ta xét một lịch sửa xe bất kì, trong đó tồn tại 2 xe \(i\) và \(i+1\) có \(A_i/B_i < A_{i+1}/B_{i+1}\). Cần chứng minh khi đổi vị trí 2 xe đó thì tổng tiền phạt sẽ giảm.

Khi đổi vị trí 2 xe, chỉ có tiền phạt của 2 xe đó bị thay đổi, còn các xe trước và sau đó vẫn giữ nguyên. Ta có:

\(X = (S + B_i)A_i + (S + B_i + B_{i+1})A_{i+1}\) là tổng tiền phạt của 2 xe \(i\) và \(i+1\) theo thứ tự ban đầu.

\(Y = (S + B_{i+1})A_{i+1} + (S + B_{i+1} + B_i)A_i\) là tổng tiền phạt của 2 xe sau khi hoán đổi vị trí cho nhau. Với \(S\) là thời gian để sửa tất cả các xe từ \(1\) đến \(i-1\)

Ta có \(X - Y = B_iA_{i+1} - B_{i+1}A_{i} > 0\) vì \(A_i/B_i < A_{i+1}/B_{i+1}\).

Vậy \(X > Y\).

main.cpp
Open in Github • Download 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define LL long long

struct car {
    int id;
    int a, b;
    double f;
    car(int id, int a, int b): id(id), a(a), b(b) {
        f = (double) a / (double) b;
    }
    bool operator > (const car &b) const {
        return f > b.f;
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> a(n), b(n);
    for (int &x: a) cin >> x;
    for (int &x: b) cin >> x;
    vector<car> cars;
    for (int i=0; i<n; i++) {
        cars.push_back(car(i, a[i], b[i]));
    }
    sort(cars.begin(), cars.end(), greater<car>());

    LL res = 0;
    LL cnt = 0;
    for (car &p: cars) {
        cnt += p.b;
        res += cnt * p.a; 
    }
    cout << res << '\n';
    for (car &p: cars) cout << p.id+1 << ' ';
    return 0;
}
Comments