c++ - 元组数

我得到了n个数a[1..n]和另外2个整数l和h。如何计算满足i

1 <= T <= 100
1 <= N <= 1000
1 <= L <= H <= 1000000
1 <= a[i] <= 1000000

PS：需要比N2logn更好的解决方案

最佳答案

解决方案
由于我的C/C++有点生疏，这主要是一个算法问题，所以我将用伪代码（主要是正确的C/C++）编写一些算法，这些算法需要一段时间才能写出。
如果你至少有SIEZOF（int）* 10 ^ 12字节的内存和可用的时间，你可以使用这个算法的时间复杂度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;

关于c++ - 元组数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13216041/