比赛 20111108 评测结果 AAAAAAAAAW
题目名称 数对的个数 最终得分 90
用户昵称 Yeehok 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-11-08 11:31:28
显示代码纯文本
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define MaxInt 200001
using namespace std;
int num[MaxInt],n,c;
bool flag[MaxInt]={0};
int cmpp(const void *a,const void *b)
{
	return (* (int *)b-* (int *)a);
}
int cmp(const void *a,const void *b)
{
	return (* (int *)a-* (int *)b);
}
int find(int *a,int len,int n)//若返回值为x,则a[x]>=n>a[x-1]
{
	int left=0,right=len,mid=(left+right)/2;
	while(left<=right)
	{
		if(n>a[mid]) left=mid+1;
		else if(n<a[mid]) right=mid-1;
		else return mid;
		mid=(left+right)/2;
	}
	return left; 
}
int main()
{
	freopen("dec.in","r",stdin);
	freopen("dec.out","w",stdout);
	scanf("%d%d",&n,&c);
	int i,j,s=0;
	for(i=0;i<n;i++)
		scanf("%d",&num[i]);
	if(n<=2000)
	{
		qsort(num,n,sizeof(int),cmpp);
		for(i=0;i<n;i++)
		{
			for(j=i+1;j<n;j++)
			{
				if(num[i]-num[j]==c)
					s++;
				if(num[i]-num[j]>c)
					break;
			}
		}
	}
	else
	{
		qsort(num,n,sizeof(int),cmp);
		int tmp;
		for(i=0;i<n;i++)
		{
			tmp=find(num,n,num[i]-c);
			for(j=tmp;1;j++)
			{
				if(num[i]-c==num[j])
				{
					s++;
				}
				else
					break;
			}
		}
	}
	printf("%d\n",s);
	return (0);
}