Editorial for linetrip: Hành trình trên trục Ox

Hiểu bài toán

Bài toán yêu cầu tìm độ dài hành trình ngắn nhất để đi từ tọa độ 0, đi qua tất cả N điểm cho trước trên trục Ox ít nhất một lần, và quay trở lại tọa độ 0. Các điểm có thể được truy cập theo bất kỳ thứ tự nào. Đây là bài toán tối ưu hóa quãng đường đi trên một chiều.

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

Cách Giải pháp quan sát trực quan (Nghiên cứu các trường hợp)

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

int abs(int n) {
    return n < 0 ? -n : n;
}

int cmpf(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int main() {
    int n, sum;
    scanf("%d", &n);
    int arr[n];
    for(int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    qsort(arr, n, sizeof(int), cmpf);

    // arr[0] là điểm âm nhỏ nhất, arr[n-1] là điểm dương lớn nhất
    if(arr[0] * arr[n-1] <= 0) { // Có cả điểm âm và điểm dương (hoặc có 0)
        sum = 2 * abs(arr[0]) + 2 * abs(arr[n-1]);
    } else if(arr[0] > 0 && arr[n-1] > 0) { // Tất cả đều dương
        sum = 2 * abs(arr[n-1]);
    } else { // Tất cả đều âm
        sum = 2 * abs(arr[0]);
    }
    printf("%d", sum);
    return 0;
}

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

Cách tiếp cận này dựa trên việc phân tích các trường hợp của các điểm trên trục số. Sau khi sắp xếp các điểm:

1. Nếu tất cả các điểm đều nằm cùng một phía so với 0 (tất cả dương hoặc tất cả âm), ta chỉ cần đi từ 0 đến điểm xa nhất và quay lại. Ví dụ: tất cả dương, đi 0 -> max -> 0, quãng đường là 2 * max.
2. Nếu các điểm nằm ở cả hai phía (có điểm âm và dương), ta cần phải đi qua hết bên này sang bên kia. Hành trình tối ưu sẽ là: 0 -> điểm âm xa nhất -> điểm dương xa nhất -> 0. Quãng đường là 2 * |min| + 2 * max. Hoặc một cách nhìn khác: đi hết một bên rồi quay lại 0 và đi hết bên còn lại. Lưu ý rằng việc đi từ điểm âm xa nhất sang điểm dương xa nhất không qua 0 là không tối ưu bằng việc quay lại 0.

Cách Giải pháp truy vết/Quy hoạch động

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

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

    int max = -9999;
    int min = 9999;
    for(int i = 0; i < n; i++) {
        if (a[i] > max) max = a[i];
        if (a[i] < min) min = a[i];
    }

    int result;
    if (max < 0 && min < 0) { // Toàn âm
        result = 2 * abs(min);
    } else if (max > 0 && min > 0) { // Toàn dương
        result = 2 * max;
    } else { // Lẫn lộn
        result = 2 * (abs(min) + abs(max));
    }

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

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

Thay vì sử dụng qsort (O(N log N)), ta chỉ cần duyệt qua danh sách một lần để tìm giá trị nhỏ nhất (min) và lớn nhất (max). Logic tính toán quãng đường tương tự như cách tiếp cận trước:

• Nếu max < 0: tất cả đều âm, chỉ cần đi đến min (xa nhất về phía âm) và quay lại.
• Nếu min > 0: tất cả đều dương, chỉ cần đi đến max (xa nhất về phía dương) và quay lại.
• Ngược lại: có cả hai phía, quãng đường là tổng khoảng cách từ 0 đến min và từ 0 đến max, nhân đôi lên (vì phải quay lại 0).

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

Bài học kinh nghiệm

• Vì tất cả các điểm nằm trên cùng một trục thẳng, thứ tự đi qua các điểm không ảnh hưởng đến độ dài đường đi giữa chúng, miễn là ta đi từ ngoài vào trong hoặc ngược lại.
• Điểm mấu chốt là xác định hướng đi: nếu điểm nằm ở cả hai phía trục, ta phải bao phủ cả hai phía. Nếu chỉ ở một phía, ta chỉ cần đi về phía đó.
• Lượt về (return trip) luôn tính bằng cách nhân đôi quãng đường từ 0 đến điểm xa nhất (tính theo chiều kim đồng hồ hoặc ngược lại).

Lỗi thường gặp

• Quên nhân đôi quãng đường (chỉ tính một chiều đi).
• Xử lý sai trường hợp các điểm nằm cùng phía (ví dụ chỉ in ra giá trị lớn nhất thay vì nhân đôi).
• Sai quy ước dấu âm/dương khi tính toán khoảng cách.