2878 캔디캔디

2878 캔디캔디 https://www.acmicpc.net/problem/2878
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; } Colored by Color Scripter

cs

현재 sum에는 못주는 사탕의 개수가 들어있다.

잘 분배한다는 방법은 사탕을 많이 얻고싶어하는 사람에게 더 많이 주면 된다.

그 방법을 위와같이 정렬한후에 남은 사람 수로 나누어 그 값을 계산한다.

2. 생일선물
선물 가격이 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; } Colored by Color Scripter

cs

금액을 내림차순, 인덱스값도 내림차순으로 정렬하고
지속적으로 P값을 빼주면서 남은사람수로 나누어준다.

인덱스를 내림차순으로 정렬하는 이유는 동일한 금액에 대해서 뒤쪽에 있는 값이 더 작다.
(즉, 앞의 리스트사람이 많이 줄어듬 = 많이 냄)