Editorial for explore: Kỳ nghỉ của Bessie

Hiểu bài toán

Bessie muốn thăm quan tối đa số lượng thắng cảnh trên một trục tọa độ, bắt đầu từ vị trí 0. Cô có tổng thời gian là T phút. Các vị trí của thắng cảnh cho trước là x1, x2, ..., x_n. Bessie phải tuân theo quy tắc thứ tự thăm quan: cô phải đi theo thứ tự tăng dần của khoảng cách đến trại (tính theo giá trị tuyệt đối). Nếu hai thắng cảnh có cùng khoảng cách, cô có thể chọn bất kỳ (nhưng trong dữ liệu input, tất cả các khoảng cách đều phân biệt). Thời gian di chuyển là 1 đơn vị trên 1 phút, thời gian thăm quan không đáng kể. Hãy tìm số lượng thắng cảnh tối đa Bessie có thể thăm quan trong giới hạn thời gian T.

Ví dụ: T=25, các vị trí là {10, -3, 8, -7, 1}. Khoảng cách các điểm: |1|=1, |-3|=3, |8|=8, |-7|=7, |10|=10. Sắp xếp theo khoảng cách: 1 (vị trí 1), -7 (vị trí -7), -3 (vị trí -3), 8 (vị trí 8), 10 (vị trí 10). Duyệt:

1. Đi từ 0 -> 1: tốn 1. Tổng: 1. -> Hợp lệ.
2. Đi từ 1 -> -7: tốn |1 - (-7)| = 8. Tổng: 1 + 8 = 9. -> Hợp lệ.
3. Đi từ -7 -> -3: tốn |-7 - (-3)| = 4. Tổng: 9 + 4 = 13. -> Hợp lệ.
4. Đi từ -3 -> 8: tốn |-3 - 8| = 11. Tổng: 13 + 11 = 24. -> Hợp lệ.
5. Đi từ 8 -> 10: tốn |8 - 10| = 2. Tổng: 24 + 2 = 26. > 25. -> Không hợp lệ. Kết quả: 4.

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

Cách Mô phỏng theo thứ tự ưu tiên (Greedy Simulation)

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

int compare(const void *a, const void *b) {
    int x1 = *(int*)a;
    int x2 = *(int*)b;
    return abs(x1) - abs(x2);
}

int main() {
    int n;
    long long T; // Dùng long long để tránh tràn số khi tính tổng thời gian
    scanf("%lld %d", &T, &n);

    int *positions = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &positions[i]);
    }

    // Sắp xếp theo khoảng cách tuyệt đối tăng dần
    qsort(positions, n, sizeof(int), compare);

    long long current_pos = 0;
    long long time_used = 0;
    int count = 0;

    for (int i = 0; i < n; i++) {
        long long dist = abs((long long)positions[i] - current_pos);
        if (time_used + dist <= T) {
            time_used += dist;
            current_pos = positions[i];
            count++;
        } else {
            break;
        }
    }

    printf("%d\n", count);
    free(positions);
    return 0;
}

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

Đây là cách tiếp cận trực quan nhất.

1. Sắp xếp: Đọc các vị trí và sắp xếp chúng theo khoảng cách tuyệt đối tăng dần so với trại (0). Hàm compare trong code sử dụng abs(x1) - abs(x2) để đảm bảo điều này.
2. Mô phỏng: Duyệt qua danh sách đã sắp xếp. Giả sử Bessie đang ở vị trí current_pos (ban đầu là 0) và đã dùng time_used phút.
3. Kiểm tra: Với mỗi điểm đến tiếp theo positions[i], tính khoảng cách di chuyển là abs(positions[i] - current_pos). Nếu time_used + khoảng_cách <= T, cô sẽ di chuyển đến điểm đó, cập nhật lại current_pos và time_used. Tăng biến đếm số lượng thắng cảnh.
4. Ngắt quãng: Nếu thời gian không đủ, dừng lại và in kết quả. Lưu ý: Vì tổng thời gian có thể lên tới 10^9 và có thể cộng dồn nhiều quãng đường (tối đa 50000 quãng, mỗi quãng tối đa 210^5), tổng thời gian có thể vượt quá giới hạn của int (210^9), nên cần sử dụng long long cho biến thời gian.

Cách Tối ưu tính toán thời gian di chuyển

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

int cmp(const void *a, const void *b) {
    int *x = (int*)a;
    int *y = (int*)b;
    return abs(*x) - abs(*y);
}

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

    // Mảng b lưu tổng thời gian để đến được điểm thứ i (tính từ điểm 0)
    // Tuy nhiên, cách tính trong code mẫu hơi khác một chút:
    // Nó tính thời gian tích lũy từ điểm đầu tiên.
    // Code gốc: b[0] = abs(a[0]); b[i] = abs(a[i]-a[i-1]) + b[i-1];
    // Điều này tương đương với: tổng thời gian = khoảng cách 0->a[0] + a[0]->a[1] + ... + a[i-1]->a[i]
    // Đây là cách tính đúng.

    long long b[50005]; // Đủ cho N=50000
    b[0] = abs(a[0]);
    for (int i = 1; i < n; i++) {
        b[i] = abs(a[i] - a[i-1]) + b[i-1];
    }

    int res = 0;
    for (int i = 0; i < n; i++) {
        if (t >= b[i]) {
            res++;
        } else {
            break;
        }
    }
    printf("%d\n", res);
    return 0;
}

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

Đây là biến thể của cách tiếp cận 1, nhưng tối ưu hơn một chút trong việc tính toán.

1. Sắp xếp: Giống cách 1, sắp xếp mảng theo khoảng cách tuyệt đối.
2. Tiền xử lý tổng thời gian: Tạo một mảng phụ (ví dụ là b), trong đó b[i] là tổng thời gian cần thiết để đi từ trại (0) đến điểm thứ i trong danh sách đã sắp xếp, tuân thủ đúng thứ tự di chuyển.
   • b[0] = |x_0 - 0|
   • b[i] = b[i-1] + |x_i - x_{i-1}|
   • Mảng b sẽ có tính chất tăng dần.
3. Tìm kiếm: Duyệt mảng b, điểm đầu tiên mà tại đó b[i] > T chính là số lượng tối đa Bessie có thể thăm (vì b tăng dần, tất cả các phần tử trước đều <= T).

Cách này về tổng thể vẫn là O(N log N) do có bước sắp xếp, nhưng việc tính toán thời gian di chuyển được gom lại trong một vòng lặp riêng biệt, giúp logic rõ ràng hơn.

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

Bài học kinh nghiệm

• Thứ tự thăm quan được xác định duy nhất bởi khoảng cách tuyệt đối đến trại 0. Do đó, bước đầu tiên không thể bỏ qua là sắp xếp các vị trí theo giá trị abs(x).
• Bài toán có tính chất Greedy (Tham lam): Một khi đã chọn đi đến một điểm theo thứ tự khoảng cách tăng dần, việc này không ảnh hưởng xấu đến khả năng đi các điểm tiếp theo. Nếu không thể đi từ điểm A đến điểm B, chắc chắn không thể đi tiếp.
• Vấn đề về tràn số: Với N lên tới 50,000 và T lên tới 10^9, tổng thời gian di chuyển tích lũy có thể vượt quá 2,147,483,647 (giới hạn của int). Cần sử dụng long long (64-bit integer) để lưu trữ tổng thời gian.

Lỗi thường gặp

• Quên sắp xếp mảng vị trí: Nếu duyệt theo thứ tự input ngẫu nhiên, kết quả sẽ sai hoàn toàn.
• Sử dụng biến kiểu int cho tổng thời gian: Dẫn đến lỗi tràn số và kết quả tính toán sai (ví dụ âm số).
• Lỗi tính toán khoảng cách: Khoảng cách từ vị trí pos_old đến pos_new là abs(pos_new - pos_old), không phải là abs(pos_new) - abs(pos_old).