#include <iostream>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;

vector<unsigned long> nums;
unsigned long N;

bool Input()
{
	unsigned long tmp;
	if (!(cin>>N)) 
		return false;
	nums.clear();
	nums.reserve(N);
	for (unsigned long i=0;i<N;++i)
	{
		cin>>tmp;
		nums.push_back(tmp);
	}
	return true;
}

inline unsigned long FindMeidan(unsigned long diff, unsigned long& minCandidate, unsigned long& maxCandidate)
{
	unsigned long pos1=0,pos2=1;
	unsigned long total = 0;
	minCandidate = 0;
	maxCandidate = nums.back() - nums.front();
	for (;pos2 < nums.size(); ++ pos2)
	{
		while (nums[pos2] - nums[pos1] >= diff&&pos1<=pos2)
			++pos1;
		total += (pos2-pos1 );
// 		if (nums[pos2] - nums[pos1]  ==  diff)
// 		{
// 			found = true;
// 			continue;
// 		}
		if (nums[pos2] - nums[pos1] >minCandidate)
			minCandidate = nums[pos2] - nums[pos1];
		if (pos1>0&&nums[pos2] - nums[pos1-1] >minCandidate)
			maxCandidate = nums[pos2] - nums[pos1-1];

	}
	return total;
}
int main()
{
	while (Input())
	{
		unsigned long medianPos;
		unsigned long total = N*(N-1)/2;
		unsigned long minCandidate, maxCandidate;
		medianPos = total/2 + total%2;
		sort(nums.begin(),nums.end());
		unsigned long minDiff=0, maxDiff = nums.back() - nums.front(),tryDiff;
		while (minDiff<maxDiff)
		{
			tryDiff = (minDiff + maxDiff +1)/2;
			unsigned long lessNum = FindMeidan(tryDiff, minCandidate,maxCandidate);
			if (lessNum< medianPos)
				if (maxCandidate<=maxDiff&&maxCandidate!=nums.back() - nums.front())
					minDiff = maxCandidate;
				else
					minDiff = tryDiff;
			else
				if (minCandidate>=minDiff&&minCandidate!=0)
					maxDiff = minCandidate;
				else
					maxDiff = tryDiff -1;
		}
			if (FindMeidan(minDiff+1, minCandidate, maxCandidate) >medianPos-1 )
			    cout<<minDiff<<endl;
			else 
				cout<<minDiff+1<<endl;
	}
	return 1;
}

• Re:为什么这个会WA呢，请高手们帮忙看看 (52) ecjtuxsyuan 2008-04-26 09:39:35