Codeforces 76 B. Mice

問題

n匹のネズミがy=y0の直線上に一列に並んでいる。
m個のチーズがy=y1の直線上に一列に並んでいる。

それぞれのネズミおよびチーズの座標が与えられる。
ネズミは次のように動く。

• 最も近いチーズに向けて走る。
• チーズに最初に辿り着いたネズミは、それを食べておなか一杯になる。
• 複数のネズミが同時に一つのチーズに辿り着いたら、分け合って全部のネズミがおなか一杯になることができる。
• 最も近いチーズが複数あるネズミは、おなか一杯になるネズミの数が最大になるようにチーズを選ぶ。

このとき、おなか一杯にならないネズミの数を求めよ。

方針

貪欲法による。
TopCoderでも出たことがある、辺に交差がなくて、次数が最大2の二部グラフ。

ネズミを順に見ていき、一つしかチーズがないのなら、そのチーズにネズミを割り当てる。
二つ狙えるチーズがあったら、左に共有できるチーズがあったら、左に向かわせる。
そうでないなら右のチーズに割り当てる。

を繰り返す貪欲法により解ける。

ソースコード

int n,m;
int used[100000];

void run()
{
	scanf("%d%d",&n,&m);
	int y1,y2; scanf("%d%d",&y1,&y2);
	vi mouse,cheese;
	
	rep(i,n){
		int x; scanf("%d",&x);
		mouse.pb(x);
	}
	rep(i,m){
		int x; scanf("%d",&x);
		cheese.pb(x);
	}
	memset(used,-1,sizeof(used));
	int i=0,j=0,ans=n;
	
	for(;i<n&&j<m;i++){
		while(j<m-1&&abs(mouse[i]-cheese[j+1])<abs(mouse[i]-cheese[j]))j++;
		if(used[j]==-1||used[j]==abs(mouse[i]-cheese[j])){
			used[j]=abs(mouse[i]-cheese[j]);
			ans--;
			continue;
		}
		if(j<m-1&&abs(mouse[i]-cheese[j+1])==abs(mouse[i]-cheese[j])){
			if(used[j]==abs(mouse[i]-cheese[j]))ans--;
			else{
				used[j+1]=abs(mouse[i]-cheese[j]);
				ans--;
			}
		}
		else{
			used[j]=abs(mouse[i]-cheese[j]);
		}
	}
	
	printf("%d\n",ans);
}