[PTIT Code] C04035 - Leo núi - Lập lịch tối ưu cho hai công đoạn bằng nguyên tắc Johnson

C04035 - Leo núi

Có N (1≤N≤25000) người leo lên và leo xuống trên 1 ngọn núi. Người i mất U(i) thời gian leo lên và D(i) thời gian để leo xuống. Trong một thời điểm chỉ có tối đa người 1 người có thể lên và tối đa 1 người có thể xuống (có thể 1 người lên, 1 người xuống). Những người khác có thể đứng chờ ở đỉnh ngọn núi. Thứ tự đi xuống có thể khác thứ tự đi lên. Bạn hãy xác định xem thời gian tối thiểu để cho N người lên và xuống ngọn núi là bao nhiêu.

Input: Dòng 1 ghi số N. N dòng tiếp theo chứa 2 số U(i) và D(i) (1 ≤ U(i) , D(i) ≤ 50000)

Output: Ghi ra thời gian tối thiểu có thể.

Ví dụ: (Giải thích: đi lên và xuống theo thứ tự người 3->1->2)

Input	Output
3 6 4 8 1 2 3	17

Tóm tắt đề bài:
- Có n người leo lên và xuống một ngọn núi.
- Mỗi người i:
    + Mất u[i] thời gian leo lên.
    + Mất d[i] thời gian leo xuống.
- Tại mỗi thời điểm:
    + Tối đa 1 người leo lên.
    + Tối đa 1 người leo xuống.
    + Những người khác có thể chờ trên đỉnh.
- Thứ tự đi xuống có thể khác thứ tự đi lên.
→ Yêu cầu: Tìm thời gian tối thiểu để tất cả lên và xuống.
→ Áp dụng: nguyên tắc Johnson.

Nguyên tắc Johnson (Johnson's rule):
Nguyên tắc Johnson dùng để tối ưu thứ tự xử lý các công việc qua 2 giai đoạn sao cho tổng thời gian hoàn tất nhỏ nhất.

Bài toán tổng quát:
- Có n công việc.
- Mỗi công việc gồm 2 giai đoạn:
    + Giai đoạn 1: xử lý ở máy 1 → thời gian a[i].
    + Giai đoạn 2: xử lý ở máy 2 → thời gian b[i].
- Mỗi máy chỉ làm 1 việc tại 1 thời điểm.
- Một việc phải làm ở máy 1 trước rồi mới làm ở máy 2.

Các bước thực hiện:
Bước 1: Chia thành 2 nhóm:
    + Nhóm A: nếu a[i] ≤ b[i] → làm trước.
    + Nhóm B: nếu a[i] > b[i] → làm sau.

Bước 2: Sắp xếp từng nhóm:
    + Nhóm A: sắp xếp tăng dần theo a[i].
    + Nhóm B: sắp xếp giảm dần theo b[i].

Bước 3: Nối để tìm lịch trình tối ưu: (Nhóm A) + (Nhóm B).

Cách này áp dụng trực tiếp cho bài leo núi, coi:
- Leo lên như máy 1 (a[i] = u[i])
- Leo xuống như máy 2 (b[i] = d[i])

C code:

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

int u[25001], d[25001], id[25001];

int cmp(const void *x, const void *y){
    int i=*(int*)x, j=*(int*)y;
    // Cả hai thuộc nhóm A: u <= d -> sắp tăng theo u[i]: ai lên nhanh hơn thì xếp trước
    if(u[i] <= d[i] && u[j] <= d[j]) return u[i] - u[j];
    // Cả hai thuộc nhóm B: u > d -> sắp giảm theo d[i]: ai xuống lâu hơn thì xếp trước
    if(u[i] > d[i] && u[j] > d[j]) return d[j] - d[i];
    // Một người thuộc nhóm A, một người thuộc nhóm B -> người nhóm A xếp trước
    return (u[i] <= d[i]) ? -1 : 1;
}

int main(){
    int n; scanf("%d",&n);
    for(int i = 0; i < n; i++){
        scanf("%d %d",&u[i],&d[i]);
        id[i] = i;
    }
    // Bước 1 + Bước 2: Chia nhóm và sắp xếp thứ tự
    qsort(id,n,sizeof(int),cmp);
    // Bước 3: Quá trình leo lên-xuống
    int up = 0, down = 0;
    for(int i = 0; i < n; i++){
        int k = id[i];
        up+=u[k]; // up: thời điểm người k leo lên xong và sẵn sàng để xuống
                  // down: thời điểm người trước đó xuống xong -> đường xuống trống, có thể xuông
         
        if(up>down) down=up+d[k]; // người k lên xong nhưng đường xuống có người khác -> phải chờ: bắt đầu xuống từ up, kết thúc tại up + d[k]
        else down+=d[k]; // đường xuống trống -> người k xuống ngay
    }
    printf("%d",down);
}