Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 先排序，再二分，注意有长度相等的情况。什么也不多说了，贴。。。

Posted by bjtu1 at 2009-04-07 23:03:33 on Problem 3663
```#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;
}

```

Followed by: