PKU 3579: Median

いい問題だと思います。+1やら<=やら<が結構迷うが何とかなって(1発ACしてしまった)。
やってることは二分探索してほげってるだけです。

#include<stdio.h>
#include<algorithm>
using namespace std;
int a;
int dat[100000];
long long count(int b){
	int left=0;
	int right=1;
	long long ret=0;
	while(right<a){
		while(dat[right]-dat[left]>b)left++;
		ret+=right-left;
		right++;
	}
	return ret;
}
int main(){
	while(~scanf("%d",&a)){
		for(int i=0;i<a;i++)scanf("%d",dat+i);
		std::sort(dat,dat+a);
		int left=-1;
		int right=1000000001;
		long long at=(long long)a*(long long)(a-1)/2;
		at=(at+1)/2;
		while(left+1<right){
			int M=(left+right)/2;
		//	printf("%d %d\n",M,count(M));
			int n=count(M);
			if(n>=at){
				right=M;
			}else{
				left=M;
			}
		}
		printf("%d\n",left+1);
	}
}