首页 > 代码库 > hdu 5101 Select (二分+单调)
hdu 5101 Select (二分+单调)
题意:
多多有一个智商值K。
有n个班级,第i个班级有mi个人。智商分别是v1,v2,.....vm。
多多要从这些人中选出两人。要求两人智商和大于K,并且两人不同班。问总共有多少种方案。
数据范围:
n ( 0≤n≤1000 ), k( 0≤k<2^31 )
m( 0≤m≤100 ), v[i]( 0≤v[i]<2^31 )
思路:
对于一个单调长的序列,可以很容易地统计两数之和大于K的对数(枚举第一个数,二分找到满足条件的最小的数的位置,然后它和它后面的数都是满足条件的)
故对于每个班内,从小到大排序,统计。
然后对于所有人,从小到大排序,统计。
后者统计值减去前者统计值即为答案。
代码:
int T,n,k,m;int q1[105];int q[100005];int main(){ cin>>T; while(T--){ scanf("%d%d",&n,&k); ll ans=0,ans1=0; ll c=0; rep(i,1,n){ scanf("%d",&m); rep(i,1,m){ scanf("%d",&q1[i]); q[++c]=q1[i]; } sort(q1+1,q1+1+m); rep(i,1,m-1){ int pos=upper_bound(q1+1+i,q1+1+m,k-q1[i])-q1; ans1+=(ll)(m-pos+1); } } sort(q+1,q+1+c); rep(i,1,c-1){ int pos=upper_bound(q+1+i,q+1+c,k-q[i])-q; ans+=(ll)(c-pos+1); } printf("%I64d\n",ans-ans1); }}
hdu 5101 Select (二分+单调)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。