[BOJ] 13561 House Rental

문제: https://www.acmicpc.net/problem/13561

 

 

문제 풀이:

투 포인터를 이용하여 문제를 풀 수 있다. O(n)으로 문제를 풀 수 있다.

l~r 사이에 포함되는 타입들을 1씩 증가해서 표시한다. -> kind[v[r].second]++;

 

다 포함됬으면,

제일 먼 두 타입의 위치의 합 나누기 2로 최적의 위치를 구한 후,

l++ 시켜가면서 이렇게 범위 줄여도 다 포함되는지 확인한다.

4 7 -6 2 -5 1 -3 1 -2 2 0 3 1 2 2 4

이런 케이스가 있을 수 있기 때문.

 

 

* 주의:  (l+r)/2로 위치를 찾을 때, 두 값의 합이 음수이고 2로 나누어 떨어지지 않는다면 최적의 위치보다 큰 값이 선택된다. 하지만 우리는 최대 거리가 같을 때, 더 작은 값을 출력 해줘야 하므로 -1을 해줘야한다.

 

 

소스 코드:

#include <iostream>
#include <vector>
#include <string.h>
#include <queue>
#include <algorithm>
#include <string>
#define inf 2000000000
using namespace std;

typedef pair<int, int> P;
typedef long long ll;
int n, k,cnt;
vector<P> v;
int kind[100001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> k >> n;
	
	
	for (int i = 0; i < n; i++) {
		int q, w;
		cin >> q >> w;
		v.push_back({ q,w });
	}
	sort(v.begin(), v.end());

	int l = 0,r=0;
	
	P res = make_pair(inf, inf); // 길이, 위치
	while (r < n) {
		if (!kind[v[r].second]) cnt++;

		kind[v[r].second]++;
		
		if (cnt == k) {
			while (1) {
				ll dist = v[r].first + v[l].first;
				if (res.first > v[r].first - v[l].first) {
					ll t = dist / 2;
					if (dist % 2 != 0 && dist < 0) {
						t -= 1;
					}
					res = make_pair(v[r].first - v[l].first, t);
				}
				cnt--;
				kind[v[l].second]--;
				l++;
				if (kind[v[l-1].second] == 0 || l>=r) break;
				else cnt++;
				
			}
			
		}
		r++;
	}

	cout << res.second << '\n';
	return 0;
}