[백준] 20495번 - 수열과 헌팅 (C++) 문제 및 풀이

문제) 백준 - 이분 탐색 - 수열과 헌팅

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

20495번: 수열과 헌팅

 

최대, 최소를 배열과 벡터에 저장합니다. 배열에 있는 수는 탐색할 숫자이며 벡터에 있는 수는 정렬을 하여 탐색할 범위입니다. 최솟값을 최댓값이 정렬된 벡터의 lower_bound, 최댓값을 최솟값이 정렬된 벡터의 upper_bound를 통해 인덱스를 구합니다.

 

C++ 소스코드)

	#include <bits/stdc++.h>
	#define endl "\n"
	#define ll long long
	#define INF 987654321
	#define MAX 500001
	using namespace std;
	int N;
	int small[MAX], big[MAX];
	vector<int> l, r;
	signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for(int i = 0; i < N; ++i){
	int a, b; cin >> a >> b;
	small[i] = a - b;
	big[i] = a + b;
	l.push_back(a - b);
	r.push_back(a + b);
	}
	sort(l.begin(), l.end());
	sort(r.begin(), r.end());
	for(int i = 0; i < N; ++i)
	cout << lower_bound(r.begin(), r.end(), small[i]) - r.begin() + 1 << " " << upper_bound(l.begin(), l.end(), big[i]) - l.begin() << endl;
	return 0;
	}

view raw 20495.cpp hosted with ❤ by GitHub