백준[baekjoon] 10165

 

 

 

 

 

https://www.acmicpc.net/problem/10165

 

[문제조건]

버스 정류소의 개수 N(3 ≤  N ≤  1,000,000,000), 버스 노선의 수 M(2 ≤  M ≤  500,000)

각 버스의 노선 [a,b] 단, 0 ≤  a,b ≤  N-1이고 a ≠  b

 

[문제풀이]

조건 a ≠ b 로 인하여 각 버스의 노선 [a,b]를 두 분류로 나눌수가 있다.

\[\displaystyle \begin{cases}a<b & nonePassZeroZone\\a>b & passZeroZone\end{cases}\]

ZeroZone == [n-1,0]

 

그룹 A의 특징으로는 (n-1)번과 0번사이 도로를 지나가지 않으며,

그룹 B의 특징으로는 (n-1)번과 0번사이 도로를 무조건 지나간다.

 

따라서 그룹A는 그룹 B를 포함할수 없는점을 알수가 있으며,

그룹 B가 그룹A를 포함하는 경우를 고려해야한다.

 

그룹B가 그룹A를 포함하는 경우

그룹B의 특징을 이용하여 그룹A의 노선의 생략가능조건을 파악해보자

1. 그룹A의 노선 끝점이 그룹B의 노선 끝점 이하일때

2. 그룹A의 노선 시작점이 그룹B의 노선 시작점 이상일때

 

위 조건 이외에도 그룹A노선끼리 생략되는지 그룹B노선끼리 생략되는지도 확인해보아야 한다. (코드참조)

 

#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

typedef struct pair<int, pair<int, int>> pii;  // {index, {start,end}}

bool cmp(const pii& a, const pii& b)
{
	if (a.second.first == b.second.first) 
		return a.second.second > b.second.second;
	
	return a.second.first < b.second.first;
}

int main()
{
	int n, m, b_start = 1e9+5, b_end = 0;
	scanf("%d %d", &n,&m);

	vector<bool> isCancel(m, false);
	vector <pii> A, B;

	for (int i = 0; i < m; i++) {
		int st, en;

		scanf("%d %d", &st, &en);

		if (st < en) {
			A.push_back({ i,{st,en} });
		}
		else {
			B.push_back({ i,{st,en + n} });
			b_start = min(st, b_start);
			b_end = max(en, b_end);
		}
	}

	sort(A.begin(), A.end(), cmp);
	sort(B.begin(), B.end(), cmp);

	int aSize = A.size(), aMax = -1;
	for (int i = 0; i < aSize; i++) {
		pair<int, int> range = A[i].second;

		if (range.second <= aMax || range.first >= b_start || range.second <= b_end)
			isCancel[A[i].first] = true;
		aMax = max(range.second, aMax);
	}

	int bSize = B.size(), bMax = -1;
	for (int i = 0; i < bSize; i++) {
		pair<int, int> range = B[i].second;

		if (range.second <= bMax)
			isCancel[B[i].first] = true;
		bMax = max(range.second, bMax);
	}

	for (int i = 0; i < m; i++) {
		if (!isCancel[i])
			printf("%d ", i + 1);
	}
	return 0;
}