#include<stdio.h>
#include<stdlib.h>

int num[20001];
int n;

int cmp(const void *e1,const void *e2){
	return *(int *)e1-*(int *)e2;
};

int bin(int data){
	int mid;
	int l=0;
	int r=n-1;

	while(l<=r){
		mid=(l+r)/2;
		if(num[mid]==data)
			return mid;
		else if(num[mid]>data)
			r=mid-1;
		else l=mid+1;
	}

	return l;
};



int main()
{
	int i,flag;
	int s,sum,k;


	while(scanf("%d%d",&n,&s)!=EOF){

		for(i=0;i<n;i++)
			scanf("%d",&num[i]);

		qsort(num,n,sizeof(num[0]),cmp);
		sum=0;
        for(i=0;i<n;i++){
			if(num[i]<s){
				k=bin(s-num[i]);
				if(num[k]<=s-num[i]){
					flag=0;
					while(num[k]<=s-num[i]&&k<n){
						flag=1;
					     k++;
					}
				 if(flag||k==n) k--;
				}
				else {
					while(num[k]>s-num[i]&&k>=0)
						k--;
				}
				if(k>i)
					sum+=(k-i);
			}
			else break;
		}

		printf("%d\n",sum);
	}
	return 0;
}
				

• 排了序不用二分也能过。。。 (380) a470086609 2009-06-09 11:02:12
• orz 虽然排序A过省代码省力 但不会省时间 (0) 980616701 2009-06-26 21:09:54