icpc.me 9006 - CyberFlower Algorithm

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

처음 문제를 보고 든 생각은 “다리의 높이를 기준으로 3분 탐색을 진행하여 최소값을 찾으면 되겠구나!” 였다. 하지만 자료형 변환 때문인지 팀 연습 때 3분 탐색으로 20번쯤 틀렸다…

두번째로 생각한 풀이는 첫번쨰 풀이보다 훨씬 쉽고 간단하다. 각 노드에 가중치를 부여한 후 중앙값을 구하는 방식이다.

우리가 아는 일차원 도로에서 매장 세우기 문제로 치환할 수 있는 것이다. 왼쪽 거리에 있는 집들의 가중치는 오른쪽 거리의 집의 개수인 m, 오른쪽 거리에 있는 집들의 가중치는 n이다.

왜냐하면, 왼쪽 거리에 있는 집들은 m개의 집과 연결되고, 오른쪽 거리에 있는 집들은 n개의 집과 연결되기 때문에 하나의 도로에서 같은 집이 여러개 있다고 봐도 무관하다.

코드는 무척 간단하다. 나중에 삼분탐색 코드로도 “맞았습니다!”가 뜨면 삼분탐색 코드도 올리도록 하겠다.

#include<bits/stdc++.h>
using namespace std;
const int SZ=2000005;
typedef long long ll;
pair<ll,int> arr[SZ];
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int t; cin>>t;
	while(t--){
		int n,m; cin>>n>>m;
		for(int i=0;i<n;i++){
			ll x; cin>>x;
			arr[i]={x,m};
		}
		for(int i=n;i<n+m;i++){
			ll x; cin>>x;
			arr[i]={x,n};
		}
		sort(arr,arr+n+m);
		ll xx=-(ll)n*(ll)m;
		for(int i=0;i<n+m;i++){
			xx+=arr[i].second;
			if(xx>=0){
				cout<<fixed; cout.precision(1);
				cout<<double(arr[i].first)<<'\n';
				break;
			}
		}
	}
	return 0;
}

백준 9006 다리