8628 相亲
2023-04-18 12:35:49 时间
8628 相亲
时间限制:500MS 内存限制:1000K
提交次数:409 通过次数:81
题型: 编程题 语言: G++;GCC
Description
在咱遥远破旧的小村庄,男女成婚仍是以古老的、传统的模式:相亲,合时辰八字,合得来则订婚,择日 成亲。其中最忽悠的则是合时辰八字,话说是月老决定,实则是根据某条公式,算是否合得来。通过多年 的明察暗访,终于让我知道合地辰八字的公式了。其规则如下: 1、 根据某条公式将时辰八字转化成一个整数num, 为了方便起见,以后就用这个num表示该人的时辰八字。 2、 如果男女双方的时辰八字之和等于一个给定的数sum,则称此对时辰八字合得来。否则相反。 3、 如果时辰八字合不来的人结婚,会被抓去浸猪笼的,因为会被当成是对神的亵渎。 如此可知,在咱们村一对男女可以结婚的概率是相当的小。现在你的任务是算出咱们村有多少对男女 可以结婚?
输入格式
第一行输入一个整数T(1<=T<=10),表示样例的个数。 接下来有T个样例,对于每一个样例,第一行输入两个整数n(0<n<10^5),sum(0<sum<=10^8), n 表示 咱们村的人口数,sum 表示给定的和。接下来输入n个人的信息,每个人用两个整数来表示,其中前面一 个表示性别sex(0表示女,1 表示男),后面一个表示其时辰八字num(0<=num<sum,且所有的num 的值各不相同)。为了方便起见,n 个人的信息是按照每个人的num的递增顺序给出的。
输出格式
输出占一行,表示能结婚的男女对数。(注意:没有同性的可以结婚,咱国家不允许)
输入样例
1 4 6 0 2 1 3 0 3 1 4
输出样例
2
提示
来源
王鑫杰
作者
admin
题目中有说,每个人的信息都是按顺序递增的,无疑在时间限制上把难度又降低了(虽然本来题目就不难的...) 根据题目要求写一个二分查找的函数,然后把每个男人(or女人)扫一遍就OK了。 下面上代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 int male[100000],female[100000],SUM; 6 void check(int left,int right,int i); 7 int main() 8 { 9 int t; 10 scanf("%d",&t); 11 while(t--) 12 { 13 int n,sum,i,temp1,temp2; int t1=0,t2=0; SUM=0; 14 scanf("%d %d",&n,&sum); 15 for(i=0;i<n;i++) 16 { 17 scanf("%d %d",&temp1,&temp2); 18 if(temp1==0) 19 female[t1++]=temp2; 20 else male[t2++]=temp2; 21 } 22 // 23 for(i=0;i<t2;i++) 24 check(0,t1-1,sum-male[i]); 25 26 // 27 printf("%d ",SUM); 28 } 29 return 0; 30 } 31 void check(int left,int right,int i) 32 { 33 int mid=(left+right)/2; 34 if(female[mid]==i) 35 { 36 SUM++; 37 //book[mid]=1; 38 return; 39 } 40 else if(left==mid) 41 { 42 if(female[right]==i) 43 { 44 SUM++; 45 return; 46 } 47 else return; 48 } 49 else if(female[mid]<i) 50 check(mid,right,i); 51 else if(female[mid]>i) 52 check(left,mid,i); 53 }
相关文章
- 【技术种草】cdn+轻量服务器+hugo=让博客“云原生”一下
- CLB运维&运营最佳实践 ---访问日志大洞察
- vnc方式登陆服务器
- 轻松学排序算法:眼睛直观感受几种常用排序算法
- 十二个经典的大数据项目
- 为什么使用 CDN 内容分发网络?
- 大数据——大数据默认端口号列表
- Weld 1.1.5.Final,JSR-299 的框架
- JavaFX 2012:彻底开源
- 提升as3程序性能的十大要点
- 通过凸面几何学进行独立于边际的在线多类学习
- 利用行动影响的规律性和部分已知的模型进行离线强化学习
- ModelLight:基于模型的交通信号控制的元强化学习
- 浅谈Visual Source Safe项目分支
- 基于先验知识的递归卡尔曼滤波的代理人联合状态和输入估计
- 结合网络结构和非线性恢复来提高声誉评估的性能
- 最佳实践丨云开发CloudBase多环境管理实践
- TimeVAE:用于生成多变量时间序列的变异自动编码器
- 具有线性阈值激活的神经网络:结构和算法
- 内网渗透之横向移动 -- 从域外向域内进行密码喷洒攻击