백준 25945 컨테이너 재배치

 

https://www.acmicpc.net/problem/25945

25945번: 컨테이너 재배치

풀이 

0. 핵심 아이디어

 

컨테이너들의 합을 sum이라고 할때

모든컨테이너들의 높이는 ⌊sum/n⌋ or (⌊sum/n⌋+1)일 것이다.

 

A : ⌊sum/n⌋

B : ⌊sum/n⌋+1

x : A 높이를 가지고 있는 칸의 갯수

라고 정의하면 다음과 같은 식을 만들 수 있다.

A*x + B*(n-x) = sum

 

이항정리를 통해서 x를 구하면

x = (sum - B*n)/(A-B);

 

x개의 칸이 A개의 높이를 가지고 있다.

 

입력으로 주어지는 컨테이너칸의 정보를 오름차순으로 정렬하고나서

앞에서 부터 x개는 A의 높이를 가져야하고

나머지는 B의 높이를 가져야한다.

 

앞의 x개중에서 A보다 높은게 있으면 A의 높이가 되겠금 이동시켜야되고

나머지 n-x개중에서 B보다 높은게 있으면 B의 높이가 되겠금 이동시켜야된다. 

 

---

 

이해를 돕기위해서 예제2번을 예시로 설명을하자면

sum = 35

n = 8

A = ⌊35/8⌋ = 4

B = ⌊35/8⌋ + 1 = 5

이므로

 

x = (35-5*8)/(4-5) = 5

 

오름차순으로 정렬하고

 

 

앞의 x(5)개중에서 A(4)보다 큰수가 있다면

A로 만들기 위한 만큼 블록을 옮겨줘야되고 (5) -> 1

나머지 (n-x)(3)개중에서 B(5)보다 큰수가 있다면

B로 만들기 위한 만큼 블록을 옮겨줘야됩니다. (6 6 7) -> 1 , 1 , 2

 

총 5개의 블록을 옮기게됩니다.

 

코드

#include <bits/stdc++.h>

#pragma warning(disable:4996)

using namespace std;

#define endl "\n"
#define int long long
#define float long double

const float INF = 1e10;
const int Dic[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };

int Ceil(float f)
{
	if (f == (int)f)
		return (int)f;
	else
		return (int)f + 1;
}

//////////////////////////////////////////////////////////////////////// 

int n;
vector<int> Arr;

int32_t main()
{
	ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int sum = 0;
	std::cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a;
		std::cin >> a;
		Arr.push_back(a);
		sum += a;
	}

	int A = sum / n;
	int B = Ceil((float)sum / (float)n);

	sort(Arr.begin(), Arr.end());

	int cnt = 0;
	if (A != B)
		cnt = (sum - B * n) / (A - B);
	else
		cnt = n;

	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		if (i < cnt)
		{
			if (Arr[i] > A)
				ans += Arr[i] - A;
		}
		else
		{
			if (Arr[i] > B)
				ans += Arr[i] - B;
		}
	}

	std::cout << ans << endl;
}