※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※
이번에 볼 문제는 백준 18266번 문제인 Meetings이다.
문제는 아래 링크를 확인하자.
https://www.acmicpc.net/problem/18266
18266번: Meetings
Two barns are located at positions $0$ and $L$ $(1\le L\le 10^9)$ on a one-dimensional number line. There are also $N$ cows $(1\le N\le 5\cdot 10^4)$ at distinct locations on this number line (think of the barns and cows effectively as points). Each cow $i
www.acmicpc.net
소들의 번호를 생각하지 않고 시간의 흐름에 따른 소의 위치가 어떻게 되는지만을 생각하면 소들의 움직임은 각 소가 처음 보고 있는 방향으로 (다른 소와의 만남에 상관없이) 계속 직진하는 모습과 같다는 점을 관찰하자. 잘 이해가 안된다면 두 소가 만나서 서로 뒤돌아 움직이는 모습과 두 소가 만나고 그대로 지나가는 모습은 번호를 떼고 보면 똑같아보이는 점을 생각해보자.
위의 관찰을 이용하면 왼쪽 헛간과 오른쪽 헛간에 (몇번 소인지는 몰라도) 각각 소가 들어오는 시각이 언제일지를 빠르게 구해낼 수 있다.
한편, 두 헛간 사이에 있는 소들 중 소 하나가 다음으로 헛간에 들어간다면 그 소는 맨 왼쪽의 소 또는 맨 오른쪽의 소가 될 수밖에 없음을 관찰하자. 중간에 있는 소가 순서를 바꿔 헛간으로 들어갈 수는 없기 때문이다. 이와 먼젓번에서 구한 각 헛간에 소가 들어오는 시각을 이용하면 소들이 헛간에 들어가는 순서를 시간순으로 알 수 있다. 이를 이용해 T값을 구해내자.
한편, 좌표 x, y에 있는 두 소가 시간 T 이하에 만난다는 것은 x<y이며 x에 있는 소는 오른쪽을 보고 y에 있는 소는 왼쪽을 바라보고 x+T >= y-T를 만족한다는 것과 같다. 이러한 관계를 만족하는 쌍의 수는 각 소들을 좌표 오름차순으로 살펴보면서 오른쪽을 살펴보고 있는 소들이 들어있는 monotone queue를 관리하는 것으로 빠르게 구해낼 수 있다.
아래는 제출한 소스코드이다.
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
int N; ll L, T;
int arr[50000];
int wgt[50000], total;
ll pos[50000];
int dir[50000];
queue<int> dirque;
ll dist[50000];
int psum, lll, rrr;
ll ans;
bool compD(int& x1, int& x2) {
return dist[x1] < dist[x2];
}
bool compP(int& x1, int& x2) {
return pos[x1] < pos[x2];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> L;
for (int i = 0; i < N; i++) {
arr[i] = i;
cin >> wgt[i] >> pos[i] >> dir[i];
total += wgt[i];
if (dir[i] > 0) dist[i] = L - pos[i];
else dist[i] = pos[i];
}
total = (total + 1) / 2;
sort(arr, arr + N, compD);
for (int i = 0; i < N; i++) {
int& idx = arr[i];
dirque.push(dir[idx]);
}
sort(arr, arr + N, compP);
lll = 0, rrr = N - 1;
while (psum < total) {
if (dirque.front() < 0) {
int& idx = arr[lll];
psum += wgt[idx];
lll++;
}
else {
int& idx = arr[rrr];
psum += wgt[idx];
rrr--;
}
dirque.pop();
}
sort(arr, arr + N, compD);
T = dist[arr[lll + (N - 1 - rrr) - 1]] * 2;
sort(arr, arr + N, compP);
queue<ll> que;
for (int i = 0; i < N; i++) {
int& idx = arr[i];
if (dir[idx] > 0) que.push(pos[idx]);
else {
while ((!que.empty()) && que.front() + T < pos[idx]) que.pop();
ans += que.size();
}
}
cout << ans;
}'BOJ' 카테고리의 다른 글
| [BOJ 11999 // C++] Milk Pails (Bronze) (1) | 2023.10.12 |
|---|---|
| [BOJ 18265 // C++] MooBuzz (0) | 2023.10.11 |
| [BOJ 18267 // C++] Milk Visits (0) | 2023.10.09 |
| [BOJ 3188 // C++] nule (0) | 2023.10.08 |
| [BOJ 3185 // C++] kviz (0) | 2023.10.07 |