여행경비로 지출된 총 금액을 모든 인원이 최대한 균등하게 돈을 지출하도록 만드는 문제
돈을 많이 낸 사람들과 작게 낸 사람들 중 평균값과의 차이가 더 큰 만큼 돈을 이동해야한다.
예를 들어
13.01
13
3.01
3
이렇게 돈을 냈다고 가정했을 때, 총 지출한 돈의 양은 32.02 달러이다.
이를 4로 나누게 되면 8..005달러가 되지만, 0.5센트는 없으므로 8달러와 8.01달러로 평균값을 둔다.
8달러와 8.01달러 중 작은 금액에 해당하는 8달러보다 작게낸 사람은 3.01달러와 3달러가 되고,
8.01달러보다 많이 낸 사람은 13.01달러와 13달러가 된다.
적게낸 사람들 각각 평균값과의 차이는 4.99달러, 5달러이고
많이낸 사람들 각각 평균값과의 차이는 5달러, 4.99달러이다.
적게낸 사람들의 차이값의 합은 9.99달러
많이낸 사람들의 차이값의 합은 9.99달러이므로 총 이동하는 돈의 양은 9.99달러이다.
++++++++++++++++++++++++++++++++++++++++++++++++++
적개낸 사람들의 평균값과의 차이와 많이낸 사람들의 평균값과의 차이가 서로 다른 경우가 존재할 수 있는데 예시를 들어보자.
3.01
14.00
12.03
25.05
총 합은 54.05이며 평균값은 13.5225다.
1센트 미만의 화폐단위는 없으므로 13.52와 13.53을 평균값으로 둔다.
13.52보다 작은 금액인 3.01과 12.03에 대하여 각각 차이값은 10.51, 1.49이며, 그 합은 12다.
13.53보다 큰 금액인 14.00과 25.05에 대하여 각각 차이값은 0.47, 11.52이며, 그 합은 11.99이다.
이 경우 선택해야하는 값은 12일까? 11.99일까?
만약 11.99달러를 큰 금액에 해당하는 쪽에서 작은 금액에 해당하는 쪽으로 보낸다고 생각해보자. ( 사실 돈을 적게 낸 쪽에서 많이 낸 쪽으로 주는 거긴하다. )
그럼 아마 돈의 분배상황은 다음과 같이 변할 것이다.
13.51
13.52
13.53
13.53
13.51이 평균값에 비하여 1센트가 모자란 것을 확인할 수 있다.
이러면 모든 사람들이 평균값에 해당하는 금액을 지불한 것이 되도록 분배받지 못하게 되므로, 13.53달러에 해당하는 사람이 13.51달러에 해당하는 사람에게 1센트를 줘야 한다.
그렇게 된다면 돈의 분배상황은 다음과 같이 된다.
13.52
13.52
13.52
13.53
이렇게 되면 모든 사람의 금액지불 현황이 평균값이 된다.
즉, 많이낸 쪽의 차이값과 적게낸 쪽의 차이값이 서로 다를경우 큰 값을 선택해야한다.
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
#pragma warning(disable:4996);
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cout.setf(ios::showpoint);
cout << fixed;
cout.precision(2);
int n, small, big, total;
vector<int> student;
while (1) {
cin >> n;
if (n == 0)
break;
small = big = total = 0;
student.clear();
for (int i = 0; i < n; i++) {
double money;
cin >> money;
student.push_back(money * 100 + 0.5);
total += student.back();
}
small = big = total / n;
if (total % n != 0) {
big++;
}
int big_gap, small_gap;
big_gap = small_gap = 0;
for (int i = 0; i < n; i++) {
if (student[i] < small) {
small_gap += small - student[i];
}
else if (big < student[i]) {
big_gap += student[i] - big;
}
}
int ret = max(big_gap, small_gap);
cout << '$' << ret / 100.0 << '\n';
}
return 0;
}