HDU 3763 CDs
2024-09-07 19:46:02
http://acm.hdu.edu.cn/showproblem.php?pid=3763
题意:
两组数据
看重复的有多少
如果每输入一个就去查找的话O(n^2) 会超时
所以可以用二法
第一组数据输入
然后第二组数据输入 在第一组数据用二分查 这样O(n*logn)
不能用set等容器 虽然时间复杂度是一样的但是 MLE
还有一种O(n)的做法
枚举a数组中的元素,然后用一个指针指向b数组中第一个大于等于a数组当前元素的数,不断移动这个指针即可
#include <iostream>
#include <stdio.h> using namespace std; int a[];
int b[];
int n;
bool search(int x)
{
int l = , r = n-;
int mid = (l+r)/;
while(l <= r)
{
if (a[mid] < x){
l = mid+;
mid = (l+r) / ;
}
else if (a[mid] > x)
{
r = mid-;
mid = (l+r)/;
}
else return true;
}
return false; }
int main()
{
freopen("in.txt", "r", stdin);
int m, ans = ;
while(~scanf("%d%d", &n, &m))
{
ans = ;
if ( m== && n == ) break;
for (int i = ; i < n; i++)
scanf("%d", &a[i]);
int tmp;
for (int i = ; i < m; i++)
{
scanf("%d", &tmp);
if (search(tmp))
ans++;
}
printf("%d\n", ans);
}
return ;
}
最新文章
- java面试知识(来自牛客网)
- SQL Server 2008 R2——查找最小nIndex,nIndex存在而nIndex+1不存在 求最小连续数组中的最大值
- 初识Linux—1
- datagrid---写后台数据交互
- 【Android UI设计与开发】第05期:引导界面(五)实现应用程序只启动一次引导界面
- ruby self.included用法
- Global::validateEmail
- 高级停靠(Dock)技术的实现
- 记一次dedeCMS网站搭建全过程
- 动手编写插件-javascript分页插件
- over 分析函数之 lag() lead()
- Linux tomcat部署War包,Linux在Tomcat部署JavaWeb项目,Linux部署War包
- HttpServletResponse对象介绍
- DMA设计
- 一个关于cookie的坑
- Android开发 ---Fragment片段布局
- 【BZOJ】【1178】【APIO2009】convention会议中心
- Cloudstack 安装记录
- Extjs MVC模式
- 选择IM云服务供应商
热门文章
- 迭代器———更锋利的C#代码小记(3)
- springmvc、springboot静态资源访问配置
- HTTPS时代已来,你做好准备了吗?
- 设置QtreeWidget水平滚动条
- Angular JS中变量定义的基本原则
- 为什么ABAP整型的1转成string之后,后面会多个空格
- windows安装tensorflow的一个教训
- docker之启动创建容器流程
- [bzoj4899]记忆的轮廓 题解(毒瘤概率dp)
- ImportError: pycurl: libcurl link-time ssl backend (nss) is different