SPOJ.COM - Thuật toán bài ALIEN - Aliens at the train

Posted on September 25th, 2016

Đề bài:

Người ngoài hành tinh đã đi đến trái đất. Và tất cả mọi thứ đang rất hài hoà, hai loài này có thể sống được với nhau. Tuy nhiên, một người ngoài hành tinh giống cái thì không muốn nhìn thấy con người trên đường đi đến trường đại học.

Chú ý là người ngoài hành tinh phải sử dụng tàu giống như con người. Nhưng người ngoài hành tinh này có thể chọn bất kì một trạm để thoả mãn cô ta không nhìn thấy quá B người. Tuy nhiên, cô ta muốn đi xa nhất có thể trên tàu. Xin hãy giúp cô ta thực hiện nhiệm vụ này.

Đầu vào

Đầu tiên là số nguyên T biểu diễn số lượng test case, sau đó, dòng tiếp theo sẽ chứa 2 số nguyên At và Bt, lần lượt là số lượng trạm tàu (1 <= At <= 100000), và số lượng người tối đa mà người ngoài hành tinh muốn nhìn thấy(1 <= Bt <= 10000000). Sau đó, một dòng chứa At số nguyên phân biệt bởi dấu cách, biểu diễn số lượng người ở trạm thứ i.(Mỗi trạm sẽ không quá 100 người).

Đầu ra

Với mỗi test case, in ra một cặp gồm 2 số lần lượt là số lượng người mà người ngoài hành tinh sẽ gặp và số lượng trạm mà cô ta vượt qua.

Ví dụ

Đầu vào:

1 
5 100 
20 15 30 80 100

Đầu ra:

65 3

Giải thích:

  • Nếu người ngoài hành tinh này lên trạm số 1, sau đó là số 2, 3. Thì lúc này cô ta gặp 65 người. Nếu cô ta quyết định đi tiếp thì cô ta sẽ gặp 145 người. Do đó cô ta sẽ xuống tàu

  • Nếu cô ta chọn bắt đầu từ trạm số 2 với 15 người, sau đó đi tiếp lên trạm số 4 thì cô ta sẽ gặp 125 người.

  • Nhưng vì cô ta muốn gặp ít người nhất có thể và không vượt quá số người mong muốn. Nên cô ta quyết định chọn đi từ trạm 1 đến trạm 3.

Chú ý: Người ngoài hành tinh có thể chọn một trạm bất kì để xuất phát, và không thể đi lùi.

Bạn có thể tham khảo đề bài tiếng anh và submit tại đây: http://www.spoj.com/problems/ALIEN/

Phân tích

Bài toán này có đặc điểm là người ngoài hành tinh chỉ đi được theo một chiều và không thể quay ngược lại. Do đó, ta có thể sử dụng phương pháp "dịch cửa sổ" (sliding-window).

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include<iostream>
using namespace std;

const int MAX = 100005;

int At;            // Số lượng trạm tàu
int Bt;            // Số lượng người tối đa mà người ngoài hành tinh muốn nhìn
int a[MAX];        // Số lượng người tại mỗi trạm

int main()
{
    ios::sync_with_stdio(false);

    // comment dòng này trước khi submit
    freopen("input.txt","r",stdin);

    int T;
    cin >> T;

    for(int tc = 0; tc < T; tc++)
    {
        cin >> At >> Bt;
        for(int i = 0; i < At; i++)
            cin >> a[i];

        int max_path = 0;            // Đường đi dài nhất
        int min_sum  = Bt + 1;        // Số lượng người ít nhất đã gặp

        int i = 0, st = 0;
        int sum = 0;                // Số lượng người đã gặp

        while(i < At)
        {
            sum += a[i];

            // kiểm tra cho đến khi
            // tổng số người đã gặp > số lượng mong muốn
            if(sum > Bt)
            {
                // độ dài đường đi hiện tại
                int path = i - st;

                // số lượng người đã gặp hiện tại
                int people = sum - a[i];

                // Kiểm tra nếu đường đi dài hơn thì cập nhật
                // trường hợp đường đi bằng nhau thì chọn đường
                // có số lượng người gặp ít hơn
                if(path > max_path)
                {
                    max_path = path;
                    min_sum = people;
                }
                else if(path == max_path)
                {
                    if(people < min_sum) min_sum = people;
                }

                // tăng điểm bắt đầu cho đến khi
                //tổng số người < số lượng mong muốn để duyệt tiếp
                while(sum > Bt)
                {
                    sum -= a[st];
                    st++;
                }
            }

            i++;
        }

        // Kiểm tra lần cuối cùng
        int path = i - st;
        if(path > max_path)
        {
            max_path = path;
            min_sum  = sum;
        }
        else if(path == max_path)
        {
            if(sum < min_sum) min_sum = sum;
        }

        cout << min_sum << " "  << max_path << endl;

    }

    return 0;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé:

Spoj
Greedy