Количество способов сделать треугольник невозможно?

Question

Дано n и массив из n положительных целых чисел, количество способов выбрать три числа, чтобы они не могли образовать треугольник.

Пример:

3 
4 2 10 

Ответ:

1 

Мой подход (в JAVA)

int[] arr = new int[n];//list of the numbers given 
int count=0;//count of all such triplets 
for(int i=0;i<n;i++) 
    arr[i]=sc.nextInt(); 
Arrays.sort(arr); 
for(int i=n-1;i>=0;i--) 
{ 
    int j=0; 
    int k= i-1; 
    while(j<k && k>=0) 
    { 
     if(arr[i]>=arr[j]+arr[k])//condition for no triangle formation 
      { 
       count++; 
       j++;//checking the next possible triplet by varying the third number 
      } 
      else if(arr[i]<arr[j]+arr[k]) 
      { 
       j=0; 
       k--;//now varying the second number if no such third number exists 
      } 
    } 
} 
System.out.println(count); 

Мой алгоритм:

После сортировки списка я тр ying, чтобы найти все числа, меньшие, чем arr[i], такие, что arr[i]>=arr[j]+arr[k], и в этом случае треугольник не образуется.

Но для этого решения я получаю timed-out. Может ли кто-нибудь предложить лучший подход к этой проблеме?

Answer 1

Соответствующий псевдо-код будет:

SORT array //nlogn 
INT counter = n*(n-1)*(n-2)/6; 
FOR i = n - 1; i >= 2; i-- DO //largest length in a triangle - there must be two lower 
    currentLargestNumber = array[i]; 
    FOR j = i - 1; j >= 1; j-- DO 
     BINARY SEARCH FOR SMALLEST k for which array[k] + array[j] > array[i] 
     counter -= j - k; 
     IF nothingAddedInTheLastIteration DO 
      BREAK; 
     END_IF 
    END_FOR 
    IF nothingAddedInTheLastIteration DO 
     BREAK; 
    END_IF 
END_FOR 

Я предположил, что не будет вводиться с более чем 3 одинаковых значений. Если есть такая возможность, удалите ненужные значения.

В каждом цикле вы должны проверить, был ли добавлен какой-либо треугольник. Если нет, перерыв в этом цикле.

Answer 2

Проблема может быть решена с помощью два указателя техники, но вместо того чтобы считать, сколько триплеты не может сформировать треугольник, мы будем смотреть на противоположное, и в конце вычтем из C(n,3) = (n)(n-1)(n-2)/6. Давайте отсортируем массив arr, arr[0] < arr[1] .. < arr[n-1]. А для данной пары i < j найти индекс k > j, s.t. arr[i] + arr[j] <= arr[k] и arr[i] + arr[j] > arr[k-1]. Это приведет к дополнительным k - j -1 троек (тройни: {i,j,j+1},{i,j,j+2},..,{i,j,k-1} Теперь обратите внимание, что всякий раз, когда мы увеличиваем j, нам не нужно, чтобы сбросить значение k, что помогает сохранить общее время сложность O(n^2)

//arr is already sorted 
long triangles = 0; 
for(int i = 0; i < n-2; i++){ 
    int k = i + 2; 
    for(int j = i + 1; j < n; j++){ 
     while(arr[i] + arr[j] > arr[k] && k < n){ 
     k++; 
     } 
     triangles += k-j-1; 
    } 
} 
long answer = n*(n-1)*(n-2)/6 - triangles;