[BOJ] 10800 : 컬러볼
풀이
다음에 다시 풀어보고 싶어서 남겨둔다.
반례를 잘 못찾아서 많이 틀린 문제로 다음에는 더깔금하게 풀어보고 싶다.
유용한 반례 코드 하단에 놓아두었으니 막힐때는 시도해보자.
코드
누적합
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
vector<pair<pair<int,int>, int>> v;
int ans[200000];
int colorBall[200001];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int color, num;
cin >> color >> num;
v.push_back({ {num,color}, i });
}
sort(v.begin(), v.end());
int sum = 0;
int same = 0;
int sameSum = 0;
int scflag = 0;
int scSum = 0;
int lastColor = 0;
//작은숫자부터 보면서 누적합한다
for (int i = 0; i < n; i++) {
int num = v[i].first.first;
int color = v[i].first.second;
if (num == same) {
sameSum += num;
if (lastColor == color) {
scflag = 1;
scSum += num;
}
else {
scSum = 0;
}
}
else {
same = num;
sameSum = 0;
scSum = 0;
}
int idx = v[i].second;
ans[idx] = sum - colorBall[color] - sameSum;
if (scflag) {
ans[idx] += scSum;
scflag = 0;
}
sum += num;
colorBall[color] += num;
lastColor = color;
}
for (int i = 0; i < n; i++) {
cout << ans[i] << '\n';
}
return 0;
}
//유용한 반례
//8
//1 3
//4 8
//1 10
//2 10
//2 10
//2 10
//3 10
//3 15
Written on June 23, 2021