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

07/12/2016 3 minutes read
Share:

Đề 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;
}
view raw HOTELS.cpp hosted with ❤ by GitHub

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

Share: