SPOJ.COM - Thuật toán bài CODFURY - Megatron and his rage

Đề bài:

Bị làm tức điên lên sau thất bại bởi cuộc tấn công của Decepticons, Megatron đã quyết định phá hủy tất cả những hành tinh trên đường trở về trái đất từ Cybertron. Có nhiều hành tinh giữa trái đất và Cybertron. Mỗi hành tinh có một vài con robot canh giữ trên đó. Bởi vì Megatron còn rất ít đạn dược nên anh ta muốn tấn công với ít robot nhất có thể. Biết anh ta không thể tấn công quá M robot.

Bạn hãy tìm ra số lớn nhất của những hành tinh mà anh ta có thể phá hủy trên hành trình của mình.

Chú ý: Megatron có thể bắt đầu cuộc tấn công từ bất kì một hành tinh nào. Và anh ta chỉ có thể di chuyển đến hành tinh bên cạnh hành tinh hiện tại anh ta đang ở đó.

Đầu vào

Đầu tiên là số T, là số lượng test case, T <= 20. Sau đó là T test case. Mỗi test case bắt đầu bằng một dòng chứa 2 số nguyên P và M. Trong đó, P là số lượng hành tinh và M là số lượng hành tinh tối đa mà anh ta có thể phá hủy. Với P <= 50000 và M <= 1000000. Sau đó là một dòng chứa P số nguyên phân biệt nhau bởi dấu cách, miêu tả số lượng robot trên mỗi hành tinh, giá trị này <= 1000.

Đầu ra

Đầu ra sẽ bao gồm T cặp số nguyên, một cặp trên một dòng xác định số lượng robot mà Megatron sẽ đánh và số hành tinh anh ta phá hủy.

Ví dụ

Đầu vào:

1
4 50
20 5 23 45

Đầu ra:

48 3

Giải thích:

• Megatron bắt đầu từ hành tinh số 1, sau đó là hành tinh số 2, 3. Tại điểm này anh ta đã đánh được 48 robot. Lúc này anh ta đã phá hủy được 3 hành tinh rồi.

• Megatron có thể bắt đầu từ hành tinh số 2 sau đó đến hành tinh số 3, 4. Tuy nhiên lúc này anh ta phải đánh 73 robot. Tuy nhiên anh ta muốn đánh số robot ít nhất nên anh ta sẽ chọn đánh từ hành tinh số 1 đến 2, 3.

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

Phân tích

• Bài toán này sử dụng thuật toán tham lam Greedy để giải. Cụ thể hơn là sử dụng phương pháp dịch cửa sổ. Cửa sổ ở đây có kích thước là M. Và ta sẽ dịch từ đầu đến cuối, rồi tìm ra trường hợp nào cho tổng robot là nhỏ nhất.

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 T, P, M;
	scanf("%d",&T);
	for(int tc = 0; tc < T; tc++)
	{
		scanf("%d%d",&P,&M);

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

		int st = 0, i = 0, sum = 0;
		int max_plannet = 0;
		int min_ammo = M + 1;
		while(i < P)
		{
			sum += a[i];
			if(sum > M)
			{
				int temp = i - st;
				int t = sum - a[i];
				if(temp > max_plannet)
				{
					max_plannet = temp;
					min_ammo = t;
				}
				else if(temp == max_plannet)
				{
					max_plannet = temp;
					if (t < min_ammo) min_ammo = t;
				}

				while(sum >= M)
				{
					sum -= a[st];
					st++;
				}
			}

			i++;
		}

		int temp = i - st;
		if(temp > max_plannet)
		{
			max_plannet = temp;
			min_ammo = sum;
		}
		else if(temp == max_plannet)
		{
			max_plannet = temp;
			if (sum < min_ammo) min_ammo = sum;
		}

		printf("%d %d\n",min_ammo,max_plannet);
		delete[] a;
	}
	return 0;
}