[BJ15975] 화살표 그리기
2019. 7. 25. 00:52ㆍComputerScience/Algorithm
https://www.acmicpc.net/problem/15975
15975번: 화살표 그리기
직선위에 $N$개의 점들이 주어지고 각 점은 $N$개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 $N$까지의 수로 표시 하고, 점들의 좌표는 모두 다르다. 각 점 $p$에 대해서, $p$에서 시작하는 직선 화살표를 이용해서 다른 점 $q$에 연결하려고 한다. 여기서, 점 $q$는 $p$와 같은 색깔의 점들 중 $p$와 거리가 가장 가까운 점이어야 한다. 만약 가장 가까운 점이 두 개 이상이면 아무거나 하나를 선택한다. 각 점 $p$에서 시작하여 위
www.acmicpc.net
데이터 범위를 신경씁시다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <set>
using namespace std;
#define pii pair<int,int>
int n;
int main() {
cin >> n;
vector<vector<long long>> arr(100001);
long long a, b, ans =0;
for (int i = 0; i < n; i++) {
cin >> a >> b;
arr[b].push_back(a);
}
for (int i = 1; i <= n; i++) {
if (arr[i].size() <= 1) continue;
sort(arr[i].begin(), arr[i].end());
ans += arr[i][1] - arr[i][0];
for (int j = 1; j < arr[i].size()-1; j++) {
long long tmp = min(arr[i][j] - arr[i][j-1],arr[i][j+1]-arr[i][j]);
ans += tmp;
}
ans += arr[i][arr[i].size() - 1] - arr[i][arr[i].size() - 2];
}
cout << ans;
}
'ComputerScience > Algorithm' 카테고리의 다른 글
| [BOJ2580] 스도쿠 (0) | 2020.10.28 |
|---|---|
| [BJ 15971] 두 로봇 (0) | 2019.07.24 |
| [BJ15973] 두 박스 . (0) | 2019.07.24 |