c++ - タプルの数

Question

N個の数a[1..N]と他の2つの整数LとHが与えられます。i<j<kおよびL<=a [i] +を満たすタプル（i、j、k）の数を数えるにはどうすればよいですか。 a [j] + a[k]<=H。

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

PS：N2lognよりも優れたソリューションが必要

Answer 1

解決

私のC/C ++はやや錆びており、これは主にアルゴリズムの質問であるため、擬似コードで記述します（ほとんどの場合、書き出すのに時間がかかるアルゴリズムのビットを使用してC / C ++を修正します）。

少なくともsizeof（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;

Answer 2

int find_three(int arr[], int c, int l,int h)
{
   int i, j, e, s, k;
   int count =0;
   sort(arr,arr+c);
   c--;
   while(arr[c]>h)
   c--;
   int sum=0;
   for (int i = 0; i<=c-2;i++)
   {  sum=arr[i]+arr[i+1]+arr[i+2];
      if(sum>h)
      break;
      for(j=i+1;j<=c-1;j++)
       {  
          for(k=j+1;k<=c;k++)
          {   sum=arr[i]+arr[j]+arr[k];
              if(sum>=l &&sum<=h)
                 count++;
              if(sum>h)
              break;
          }
           if(sum>h)
              break;
       }
   }
      return  count;
}

Answer 3

基本的なアプローチ：

for (i=0; i<N; i++) {
    for (j=i+1; j<N; j++) {
        for (k=j+1; k<N; k++) {
            int sum = a[i] + a[j] + a[k];
            if (L <= sum && sum <= H) number_of_tuples++;
        }
    }
}

おそらくより良いです（間違いがあるかもしれませんが、基本的な考え方は、すでに最大値を超えている場合は壊すことです）：

for (i=0; i<N; i++) {
    if (a[i] > H) continue;
    for (j=i+1; j<N; j++) {
        if (a[i] + a[j] > H) continue;
        for (k=j+1; k<N; k++) {
            int sum = a[i] + a[j] + a[k];
            if (L <= sum && sum <= H) number_of_tuples++;
        }
    }
}