数列求和-腾讯编程马拉松

时间：2015-10-26 05:40:44
【文件属性】：

文件名称：数列求和-腾讯编程马拉松

文件大小：2KB

文件格式：CPP

更新时间：2015-10-26 05:40:44

数列求和 编程马拉松 C++

给定n个数字和一个范围[x,y]，求从这n个数字中任意取出一些数字，使得它们的和在范围[x,y]中有多少种取法。 输入： 输入第一行为整数case，case<=10 表示有case组测试数据。 对于每一组测试数据，第一行为一个整数n (n<=30)，第二行为n个整数a[i]，第三行为两个整数x和y。其中，a[i]>=0，sum(a[i])<2^31，0。 输出： 对于每组数据输出一行，总的取法数。 样例输入： 2 3 1 2 4 1 7 3 1 2 4 2 5 样例输出： 7 4

立即下载

网友评论

  • 运用了很多STL，不错
  • 感谢分享。看了下，大概就是把数组分成前后两部分运行；之后把每部分的所有组合的值保留起来放在leftSet和rightSet里，如果两个集合里有一对元素的和满足条件则加到总结果中去。代码中对集合进行了排序以加快寻找符合条件对的过程。如果在寻找符合条件对的时候用二分查找，则可变成 a(n) = 2*a(n/2) + O((n/2)!)，则复杂度可将为O(logn * (n/2)!)。（后面部分只是粗略算了下，如果错了请轻拍-_-||）
  • 可以运行，没有注释。
  • 可以运行，但是没有注释，没有讲实现原理。

相关文章