icpc.me 16210 - CyberFlower Algorithm

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

정작 제가 고등학생때는 대구과학고등학교 코드잼은 남의 일이라고 생각했는데, 대학생이 되어 후배님들이 내신 문제를 푸니 재밌네요. (여담이지만 저는 제가 컴퓨터 관련학과로 오게 될 줄 몰랐습니다…)

좌표압축은 아니지만 좌표 압축 아이디어를 사용하면 쉽습니다. 모든 x,y를 정렬해서 저장하면 $x_i, y_i$보다 작은 수의 개수를 lower_bound를 이용해서 log(n)으로 구할 수 있습니다.

위에서 구한 개수를 이용하면 수식을 O(1)의 시간복잡도로 구할 수 있습니다.

prefix sum을 이용하여 $x_1$~$x_i$ 까지의 합을 저장해 둡니다. 그 후 log(n)의 시간복자도로 x보다 작은 x좌표의 개수 a를 구합니다.

이제 택시거리 식은 $ pre[n]-2pre[a]+(2a-n)* x $ 라는 식으로 변경할 수 있습니다.

y축도 마찬가지 입니다.

#include<bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
using namespace std;
const int SZ=500005;
typedef long long ll;
vector<ll> vx,vy;
pair<ll,ll> arr[SZ];
ll prex[SZ];
ll prey[SZ];
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	int n; cin>>n;
	for(int i=1;i<=n;i++){
		ll x,y; cin>>x>>y;
		arr[i]={x,y};
		vx.pb(x); vy.pb(y);
	}
	sort(vx.begin(),vx.end());
	sort(vy.begin(),vy.end());
	for(int i=0;i<n;i++){
		prex[i+1]=prex[i]+vx[i];
		prey[i+1]=prey[i]+vy[i];
	}
	ll tx=prex[n],ty=prey[n];
	ll ans=(ll)(1e16+5); int p=0;
	for(int i=1;i<=n;i++){
		int a=lower_bound(vx.begin(),vx.end(),arr[i].ff)-vx.begin();
		int b=lower_bound(vy.begin(),vy.end(),arr[i].ss)-vy.begin();
		ll dst=tx-2LL*prex[a]+(ll)(2*a-n)*arr[i].ff+ty-2LL*prey[b]+(ll)(2*b-n)*arr[i].ss;
		if(ans>dst){
			ans=dst;
			p=i;
		}
	}
	cout<<p;
	return 0;
}

백준 16210 DSHS Bank