SPOJ.COM - Thuật toán bài MKEQUAL - Make them equal !

Đề bài:

Bạn có một dãy gồm N phần tử. Tại bất kì lượt di chuyển nào, bạn chọn ra 2 chỉ số i và j ( 0 <= i, j < N và i != j ) và tăng giá trị tại một chỉ số và giảm giá trị tại chỉ số còn lại. Bạn có thể thực hiện lần di chuyển này với số lần bất kì. Hỏi số phần tử lớn nhất có thể mà chúng có giá trị bằng nhau (sau bất kì số lần di chuyển nào).

Đầu vào

Đầu vào bao gồm số T là số lượng test case, 1 <= T <= 100. Sau đó là T test case, mỗi cái bao gồm số N - là số lượng phần tử của mảng ở dòng đầu tiên 1 <= N <= 100000. Dòng tiếp theo chứa N số nguyên được phân cách bởi dấu cách, có giá trị từ 0 đến 100000.

Đầu ra

Mỗi test case in ra trên một dòng giá trị cần tìm.

Ví dụ

Đầu vào:

1
4
1 2 3 4

Đầu ra:

3

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

Phân tích

Mình sử dụng thuật toán tham lam Greedy để giải quyết bài toán.

Mình có nhận xét là nếu như tổng của N số đó (Sum) mà chia hết cho N thì chắc chắn sẽ có cách để chuyển hết N số đó về số có giá trị (Sum / N). Do đó kết quả sẽ là N.

Ngược lại. mình có thể chuyển N số đó thành N - 1 số có giá trị (Sum / N) và số còn lại có giá trị tùy ý. Kết quả là N - 1.

Ví dụ 1: mình có dãy N = 4 số: 3 5 6 10

Tổng là Sum = 3 + 5 + 6 + 10 = 24 => Sum / N = 24 / 4 = 6. Do đó mình sẽ chuyển được hết 4 số này về giá trị = 6, bằng cách:

• Tăng 3 và giảm 10: sau 3 lần mình được dãy: 6 5 6 7
• Tăng 5 và giảm 7: sau 1 lần mình đưa được về dãy: 6 6 6 6

Vậy kết quả = N = 4

Ví dụ 2: dãy N = 4 số: 1 2 3 4

Tổng là Sum = 1 + 2 + 3 + 4 = 10 => Sum / N = 10 / 4 = 2 (chia nguyên). Do đó mình sẽ chuyển được 4 số này về dạng là có 3 số = 2 và số còn lại có giá trị khác 2.

• Tăng 1, giảm 3: sau một lần mình đã có dãy: 2 2 2 4.

Vậy kết quả = N - 1 = 3

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;

int main()
{
	ios::sync_with_stdio(false);
	//freopen("input.txt","r",stdin);
	int Testcase, n, sum;

	cin >> Testcase;
	for(int tc = 0; tc < Testcase; tc++)
	{
		cin >> n;
		sum = 0;
		for(int i = 0; i < n; i++)
		{
			int temp;
			cin >> temp;
			sum += temp;
		}
		if(sum % n == 0) cout << n << endl;
		else cout << n - 1 << endl;
	}
	return 0;
}