这道题其实就是个水题，可惜我忘了一种传说中叫双指针的东西，太弱了，呜呜。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <vector> 6 #include <map> 7 using namespace std; 8 int n; 9 long long a[5010],b[5010]; 10 int num[5010]; 11 template<class T> inline void readint(T& x) { 12 char c; 13 int mul = 1; 14 while((c = getchar()) != EOF){ 15 if(c == '-')mul = -1; 16 if(c >= '0' && c <= '9'){ 17 x = c-'0'; 18 break; 19 } 20 } 21 if(c == EOF){x = EOF;return;} 22 while(c = getchar()){ 23 if(c >= '0' && c <= '9'){ 24 x = (x<<1)+(x<<3)+(c-'0'); 25 }else break; 26 } 27 x *= mul; 28 } 29 int main(){ 30 //freopen("in.txt","r",stdin); 31 while(~scanf("%d",&n)){ 32 memset(num,0,sizeof num); 33 for(int i=0;i<n;i++) readint(a[i]),b[i]=a[i]; 34 sort(a,a+n); 35 sort(b,b+n); 36 int ct=unique(b,b+n)-b; 37 for(int i=0;i<n;i++){ 38 int x=lower_bound(b,b+ct,a[i])-b; 39 num[x]++; 40 } 41 long long ans=0; 42 for(int i=0;i<ct;i++){ 43 int j=i+1; 44 int x=lower_bound(b,b+ct,2*b[i])-b; 45 if(x<ct&&b[x]==2*b[i]){ 46 ans+=num[x]*(long long)num[i]*(num[i]-1)/2; 47 } 48 int k=lower_bound(b,b+ct,b[i]-b[j])-b; 49 for(;j<ct;j++){ 50 while(k<ct&&b[i]+b[j]>b[k]) k++; 51 if(k>=ct) continue; 52 if(b[i]+b[j]==b[k]){ 53 ans+=(long long)num[i]*num[j]*num[k]; 54 } 55 } 56 } 57 printf("%lld ",ans); 58 } 59 return 0; 60 }