枚举+二分查找。
A+B+C >= K ----> C >= K - A -B ----> 统计大于等于C的个数即可。
#include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <string> #include <algorithm> using namespace std; int a[1010]; int Scan() //输入外挂 { int res=0,ch,flag=0; if((ch=getchar())==‘-‘) flag=1; else if(ch>=‘0‘&&ch<=‘9‘) res=ch-‘0‘; while((ch=getchar())>=‘0‘&&ch<=‘9‘) res=res*10+ch-‘0‘; return flag?-res:res; } void Out(int a) //输出外挂 { if(a>9) Out(a/10); putchar(a%10+‘0‘); } int main() { int t,n,k; scanf("%d",&t); while(t--) { int ans=0; n=Scan(); k=Scan(); //scanf("%d%d",&n,&k); for(int i=0;i<n;i++) a[i]=Scan(); //scanf("%d",&a[i]); sort(a,a+n); if(k==0){printf("0\n");continue;} for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { int sum=k-a[i]-a[j]; int cnt=lower_bound(a+j+1,a+n,sum)-a; ans+=(n-cnt); } } Out(ans); printf("\n"); } return 0; }
原文:http://blog.csdn.net/imutzcy/article/details/25123339