首页 > 代码库 > XDU 1284 寻找礼物
XDU 1284 寻找礼物
枚举+二分查找。
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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。