반응형
https://www.acmicpc.net/problem/10800
10800번: 컬러볼
첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N
www.acmicpc.net
#include <bits/stdc++.h>
using namespace std;
struct Ball {
int idx, color, size;
bool operator<(const Ball& b) const {
if (size == b.size) return idx < b.idx;
else return size < b.size;
}
};
int color[200001], sum;
int ans[200001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<Ball> v;
v.push_back({ 0,0,0 });
for (int i = 1; i <= n; i++) {
int a, b;
cin >> a >> b;
v.push_back({ i,a,b });
}
sort(v.begin(), v.end());
for (int i = 1, j = 1; i <= n; i++) {
while (v[i].size > v[j].size) {
sum += v[j].size;
color[v[j].color] += v[j].size;
j++;
}
ans[v[i].idx] = sum - color[v[i].color];
}
for (int i = 1; i <= n; i++) {
cout << ans[i] << '\n';
}
return 0;
}
반응형
'Algorithm > problem' 카테고리의 다른 글
| 백준 11779번 : 최소비용 구하기2 - 다익스트라 (0) | 2022.02.15 |
|---|---|
| 백준 1916번: 최소비용 구하기 - 다익스트라 C++ (0) | 2022.02.15 |
| 백준 10166번: 관중석 문제풀이코드 C++ (0) | 2022.02.13 |
| 백준 2573번 : 빙산 - BFS 활용 C++ (0) | 2022.02.13 |
| 백준 15971번: 두 로봇 C++ 문제풀이코드 (0) | 2022.02.13 |