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 < 2³¹). Dòng tiếp theo sẽ có N số nhỏ hơn 10⁶. 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 

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

Mình 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. Mình sẽ duyệt từ đầu đến cuối. Mình 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 mình đượ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ì mình 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à mình sẽ tìm được kết quả.

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<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;
}