首页 > 代码库 > HDU 5101 水二分
HDU 5101 水二分
给定一些集合,选择两个来自不同集合的数,加和大于k,问有多少种选择方案。
ans=从所有数中选择的两个加和大于k的数的方案数-在同一个集合中选择的两个加和大于k的数的方案数
对所有数据排序后二分找即可
#include "stdio.h" #include "string.h" #include "algorithm" using namespace std; struct node { __int64 x,id; }b[101000]; __int64 a[1010][110],c[1010]; int cnt; bool cmp(node a,node b) { return a.x<b.x; } __int64 find_b(__int64 x) { __int64 l,r,mid; l=0; r=cnt-1; while (l<=r) { mid=(l+r)/2; if (b[mid].x<x) l=mid+1; else r=mid-1; } return cnt-l; } __int64 find_a(__int64 x,__int64 id) { __int64 l,r,mid; l=0; r=c[id]-1; while (l<=r) { mid=(l+r)/2; if (a[id][mid]<x) l=mid+1; else r=mid-1; } return c[id]-l; } int main() { __int64 Case,n,k,i,j,m,ans,sum,x; scanf("%I64d",&Case); while (Case--) { scanf("%I64d%I64d",&n,&k); cnt=0; for (i=1;i<=n;i++) { scanf("%I64d",&m); c[i]=m; for (j=0;j<m;j++) { scanf("%I64d",&a[i][j]); b[cnt].x=a[i][j]; b[cnt++].id=i; } sort(a[i],a[i]+m); } sort(b,b+cnt,cmp); ans=0; for (i=0;i<cnt;i++) { x=k-b[i].x+1; sum=find_b(x); sum-=find_a(x,b[i].id); ans+=sum; } printf("%I64d\n",ans/2); } return 0; }
HDU 5101 水二分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。