10800 컬러볼

10800 컬러볼 https://www.acmicpc.net/problem/10800

공의 크기와 색이 주어진다.
공은 다른 공을 잡을 수 있는데 자신 보다 크기가 작고 색이 달라야 한다.
각 공이 잡을 수 있는 공들의 크기 합을 구하는 문제이다.

누적 합과 사이즈별 공의 갯수로 잘 조리하면 풀 수 있을것 같았다.
크기 기준으로 내림차순, 색 별로 오름차순으로 정렬하였다.
그 후 누적합($sum$), 색깔별 누적합($color$_$sum[]$), 사이즈별 공 갯수($size$_$cnt[]$)를 구했다.

이제 잘 조리하면 풀 수 있을것같아 밑의 예시를 들고 풀었다.

여기서 처음 위치인 색 2, 사이즈 15인 공을 가지고 생각해보면

위와 같이 빨간색에서 노란색과 초록색값을 뺀값이 결과가 된다.

전체 누적합과 같은색 누적합은 미리 구해놨고 초록색을 구하는게 이분탐색을 써야한다.
자기 자신과 동일한 공의 갯수를 구해서 미리 구해놓은 $size$_$cnt[]$에서 뺀 후 사이즈를 곱하면 된다.

#include <cstdio> #include <algorithm> using namespace std; struct Ball {     int color, size, idx; }; bool operator<(Ball const a, Ball const b) {     if (a.size == b.size) return a.color < b.color;     return a.size > b.size; } int N; Ball ball[200001]; int color_sum[200001], sum; int size_cnt[2001]; int ans[200001]; int main() {     scanf("%d", &N);     for (int n = 1;n <= N;n++) {         scanf("%d%d", &ball[n].color, &ball[n].size);         ball[n].idx = n;         size_cnt[ball[n].size]++;     }     sort(ball + 1, ball + N + 1);       for (int n = N;n >= 1;n--) {         color_sum[ball[n].color] += ball[n].size;         sum += ball[n].size;     }     for (int n = 1;n <= N;n++) {         int lidx = lower_bound(ball + n, ball + N + 1, ball[n]) - ball;         int uidx = upper_bound(ball + n, ball + N + 1, ball[n]) - ball;         // uidx - lidx 는 [n, end] 구간에서 지금 공과 똑같은 상태의 공 갯수           ans[ball[n].idx] = sum - color_sum[ball[n].color] -                             (size_cnt[ball[n].size] - (uidx-lidx)) * ball[n].size;         sum -= ball[n].size;         color_sum[ball[n].color] -= ball[n].size;         size_cnt[ball[n].size]--;     }     for (int n = 1;n <= N;n++)         printf("%d\n", ans[n]);     return 0; } Colored by Color Scripter

cs