第7回日本情報オリンピック 春合宿 2日目 「カンニング対策」
問題文を読んで3秒で二分探索だと悟った。
こういう解法の決めつけはよくないと思うけど顕著すぎるんじゃ~
int n,m; int x[100003]; int y[100003]; bool ch(int d){ int co = 0; int h = x[0] + d; co++; for(int i = 1;i < m;i++){ if(x[i] > h){ co++; h = x[i] + d; } } h = y[0] + d; co++; for(int i = 1;i < m;i++){ if(y[i] > h){ co++; h = y[i] + d; } } return (co <= n); } int main(){ scanf("%d%d",&n,&m); for(int i = 0;i < m;i++){ scanf("%d%d",&x[i],&y[i]); } sort(x,x + m); sort(y,y + m); int lb = -1,ub = 1000000000; while(ub - lb > 1){ int mid = (lb + ub) / 2; if(ch(mid) == true)ub = mid; else lb = mid; } printf("%d\n",ub); return 0; }