Thuật toán

Chia sẻ đầy đủ về các thuật toán và lời giải các bài toán cơ bản

SPOJ.COM – Thuật toán bài HOTELS – Hotels Along the Croatian Coast

Đề bài:

Có N khách sạn dọc theo bờ biển Adriatic. Mỗi khách sạn sẽ có một giá tiền riêng. Sroljo đã trúng sổ xố được M tiền. Bây giờ anh ấy muốn mua một dãy những khách sạn liên tiếp. Sao cho tổng giá trị của chúng là lớn nhất. Nhưng chúng không được lớn hơn M.

Bạn hãy tính giá trị lớn nhất này.

Đầu vào:

Dòng đầu tiên của đầu vào là 2 số N và M (1 ≤ N ≤ 300 000, 1 ≤ M < 231). Dòng tiếp theo sẽ có N số nhỏ hơn 106. Biểu diễn giá trị của những khách sạn trên.

Đầu ra:

In ra kết quả cần tìm (biết kết quả lớn hơn 0)

Ví dụ 1:

Đầu vào:

5 12
2 1 3 4 5

Đầu ra:

12

Ví dụ 2:

Đầu vào:

4 9
7 3 5 6

Đầu ra:

8

Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://www.spoj.com/problems/HOTELS/

Phân tích:

+ Tôi sẽ sử dụng thuật toán tham lam Greedy, và thuật toán đó là thuật toán dịch cửa sổ Sliding Window. Tôi sẽ duyệt từ đầu đến cuối. Tôi sử dụng một biến trỏ vào đầu dãy, biến thứ 2 dùng để chạy từ 1 đến hết dãy. Biến thứ 2 sẽ tăng cho đến khi tổng của dãy số lớn hơn M thì dừng lại. Lúc này tôi được một giá trị là số lượng những khách sạn. Sau đó tăng con trỏ thứ nhất lên cho đến khi tổng của dãy nhỏ hơn M thì tôi lại tiếp tục tăng biến thứ 2. Quá trình duyệt tiếp tục như vậy cho đến hết là tôi sẽ tìm được kết quả.

Lời giải:

(Các 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 tôi 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 tôi 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 các bạn.)

Code C/C++:

#include<stdio.h>

int main()
{
    int n = 0, m = 0;
    scanf("%d%d",&n,&m);

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

    int st = 0;
    int i  = st;

    int sum = 0;
    int max = 0;

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

        if(sum > m)
        {
            sum -= a[i];
            if(sum > max) max = sum;

            sum += a[i];
            while(sum > m) 
                sum -= a[st++];
        }
        i++;
    }

    if(sum > max) max = sum;
    printf("%d\n",max);

    delete[] a;

    return 0;
}

Code by Phạm Văn Lâm.

513 views

1 bình luận

  1. Phạm Văn Lâm

    Trên đây là đề bài và lời giải bài HOTELS – Hotels Along the Croatian Coast trên trang spoj.com. Rất mong nhận được sự ủng hộ và phản hồi từ các bạn.

    Trân trọng,
    Phạm Văn Lâm.

Để lại bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *