3298149_ac_610ms_464k.cpp

来自「北大大牛代码 1240道题的原代码 超级权威」· C++ 代码 · 共 54 行

#include <stdio.h>
#include <algorithm>
#define maxn 100001
using namespace std;

typedef __int64 Int;

int n;
Int num[maxn];

int main()
{
	int i, l, r, m;
	Int min, mid, max, tmp, cnt, tot;

	while(scanf("%d",&n)==1)
	{
		for(i = 0; i < n; i++)
		{
			scanf("%I64d",&num[i]);
		}
		tot = (n*(n-1)/2+1)/2;
		sort(num,num+n);
		min = 0;max = num[n-1]-num[0];
		while(min < max)
		{
			mid = (min+max)/2;
			cnt = 0;
			for(i = 0; i < n; i++)
			{
				tmp = num[i]+mid;
				l = i; r = n;
				while(l < r)
				{
					m = (l+r)>>1;
					if(num[m] > tmp)
						r = m;
					else
						l = m+1;
				}
				cnt += l-i-1;
				if(cnt >= tot)
					break;
			}
			if(cnt >= tot)
				max = mid;
			else
				min = mid+1;
		}
		printf("%I64d\n",min);
	}
	return 0;
}