3661 생일선물 https://www.acmicpc.net/problem/3661
1. 캔디캔디
사탕 $M$개로 친구들에게 나누어줬을 때 친구들이 원하는 사탕을 받지 못한 수의 제곱만큼 분노가 찬다.
이 분노들의 합을 최소화 시키는 문제이다.
굉장히 어렵게 느껴졌었다.
친구$i$가 얻고 싶은 사탕을 $candy_{i}$라 하면 $min \sum_{i=1}^{N} (candy_{i} - give_{i})^2$, $\sum_{i=1}^{N} give_{i} = M$이다.
줄 수 있는 사탕과 친구들이 얻고싶은 사탕은 정해져있으므로 못주는 사탕 또한 정해져있다.
못주는 사탕을 잘 분배해서 최솟값을 만들면 된다.
코드를 먼저 보겠다.
#include <cstdio>
#include <algorithm>
using namespace std;
int M, N;
int candy[100001];
int main() {
scanf("%d%d", &M, &N);
long long sum = -M;
for (int n = 0;n < N;n++) scanf("%d", &candy[n]), sum += (long long)candy[n];
sort(candy, candy + N);
long long ans = 0;
for (int n = 0;n < N;n++) {
long long w = min((long long)candy[n], sum / (N - n));
ans += w*w;
sum -= w;
}
printf("%lld\n", ans);
return 0;
}
| cs |
현재 sum에는 못주는 사탕의 개수가 들어있다.
잘 분배한다는 방법은 사탕을 많이 얻고싶어하는 사람에게 더 많이 주면 된다.
그 방법을 위와같이 정렬한후에 남은 사람 수로 나누어 그 값을 계산한다.
선물 가격이 P이고 N명의 사람들이 낼 수 있는 최대금액들이 정해져있다.
각 사람이 내는 금액과 P/N의 최댓값을 최소화 시키도록 하는 문제다.
위 문제처럼 정렬한 후에 적당하게 나눠주면 풀 수있다.
최댓값이 동일하면 돈을 많이 낼 수 있는사람이 더 내고
이마저도 동일하면 리스트 앞에 있는사람이 돈을 더 낸다는 조건이 있다.
코드를 먼저 보겠다.
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int N, P;
int ans[101];
pair<int, int> g[101];
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &P, &N);
for (int n = 0;n < N;n++) {
scanf("%d", &g[n].second), g[n].first = n;
}
sort(g, g + N, [](pair<int, int> &a, pair<int, int> &b)->bool {
return a.second == b.second ? a.first > b.first : b.second > a.second;
});
for (int n = 0;n < N;n++) {
ans[g[n].first] = min(g[n].second, P / (N - n));
P -= ans[g[n].first];
}
if (P != 0) printf("IMPOSSIBLE\n");
else {
for (int n = 0;n < N;n++) printf("%d ", ans[n]);
printf("\n");
}
}
return 0;
}
| cs |
지속적으로 P값을 빼주면서 남은사람수로 나누어준다.
인덱스를 내림차순으로 정렬하는 이유는 동일한 금액에 대해서 뒤쪽에 있는 값이 더 작다.
(즉, 앞의 리스트사람이 많이 줄어듬 = 많이 냄)
