cpper编程论坛 - 查看单个帖子

liuxinyu · #9 (**permalink**) 2008-06-14

引用:

作者: sankt

偶再来补充一题：

给定两个数组：
int a[] = {a1,a2,a3,...,an};
int b[] = {b1,b2,b3,...,bn};
给定一个数B
要求：
1. 求出所有满足这个关系 ai + bj <= B的数对（ai,bj）i,j不一定要相等；
2. 复杂度为O(n+k) k为数据对的个数；

我也觉得好像少条件了。跑个题啊，这个题目拿Haskell写特别直接：

代码:

bar xs ys a= [(x,y) | x <- xs, y <- ys, x+y<=a]

直接运行结果如下：

代码:

Bar> bar [4,1,2,5,3,8] [5,6,9,20,7] 15
[(4,5),(4,6),(4,9),(4,7),(1,5),(1,6),(1,9),(1,7),(2,5),(2,6),(2,9),(2,7),(5,5),(5,6),(5,9),(5,7),(3,5),(3,6),(3,9),(3,7),(8,5),(8,6),(8,7)]
Bar> length (bar [4,1,2,5,3,8] [5,6,9,20,7] 15)
23