[BOJ] 10800 : 컬러볼

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