元组数 [英] Number of tuples
问题描述
我给N个数A [1..1]和2个其它整数L和H.我怎么能算元组(I,J,K)满足I&LT数量; J< k和L&其中; = A [1] + A [j]的一个+ [k]的&其中; = H
I am given N numbers a[1..N] and 2 other integers L and H. How can I Count the number of tuples (i,j,k) satisfying i < j < k and L <= a[i] + a[j] + a[k] <= H.
1 <= T <= 100
1 <= N <= 1000
1 <= L <= H <= 1000000
1 <= a[i] <= 1000000
PS:需要比N2logn更好的解决方案。
PS: Need Better Solution than N2logn
推荐答案
解决方案
由于我的C / C ++是有点生疏,这主要是一个算法的问题,我会在伪code(主要是正确的C / C ++与算法位,将需要一段时间才能写出来)写的。
Since my C/C++ is somewhat rusty and this is primarily an algorithms question, I will write in pseudocode (mostly correct C/C++ with bits of algorithms that would take a while to write out).
如果您有至少的sizeof(int)的* 10 ^ 12字节的内存和可用时间,你可以使用这个算法的时间复杂度为O(n ^ 2 *的log(n))。
If you have at least sizeof(int)*10^12 bytes of memory and time available, you can use this algorithm with time complexity O(n^2 * log(n)).
// Sort the N numbers using your favorite, efficient sorting method. (Quicksort, mergesort, etc.) [O(n*log(n))].
int[] b = sort(a)
int[] c = int[length(b)^2];
// Compute the sums of all of the numbers (O(n^2))
for(int i = 0; i < length(b); i++){
for (int j = i; j < length(b); j++){
c[i*length(b)+j] = b[i]+b[j];
}
}
// Sort the sum list (you can do the sorts in-place if you are comfortable) - O(n^2*log(n))
d = sort(c);
// For each number in your list, grab the list of of sums so that L<=num+sum<=H O(n)
// Use binary search to find the lower, upper bounds O(log(n))
// (Total complexity for this part: O(n*log(n))
int total = 0;
for (int i = 0; i < b; i++){
int min_index = binary_search(L-b[i]); // search for largest number <= L-b[i]
int max_index = binary_search(H-b[i]); // search for smallest number >= H-b[i]
total += max_index - min_index + 1; // NOTE: This does not handle edge cases like not finding any sums that work
}
return total;
这篇关于元组数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!