比赛 20111108 评测结果 AAAAAAAAAT
题目名称 数对的个数 最终得分 90
用户昵称 magic 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-11-08 10:22:41
显示代码纯文本
#include<iostream>
#include<cstdio>
using namespace std;
const int maxlong=100000000;
int data[200005],ans,n,c;
void qsort(int a[],int l,int r);	
void qsort(int a[],int l,int r)
{
	int i,j,x,y;
	i=l;j=r;x=a[(l+r)/2];
	while (i<=j)
	{ 
		while (a[i]<x) i++;
		while (a[j]>x) j--;	
		if (i<=j)
		{
			y=a[i];a[i]=a[j];a[j]=y;
			i++;j--;
		}
	}
	if (l<j) qsort(a,l,j);
	if (i<r) qsort(a,i,r);
}
int main()
{
	freopen("dec.in","r",stdin);
	freopen("dec.out","w",stdout);
	scanf("%d%d",&n,&c);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&data[i]);
	}
	qsort(data,1,n);
	int le,ri,mid;
	data[n+1]=maxlong;
	for (int i=1;i<=n;i++)
	{
		le=i+1;
		ri=n;
		while (le<ri)
		{
			mid=(le+ri)/2;
			if (data[mid]-data[i]>=c)
			{
				ri=mid;
			}
			else 
			{
				le=mid+1;
			}
		}
		for (int j=le;j<=n;j++)
		{
			if (data[j]-data[i]==c)
			{
				ans++;
			}
			else 
			{
				break;
			}
		}
	}
	if (c==0) ans*=2;
	printf("%d",ans);
	return 0;
}