삼각형을 만들 수없는 방법의 수는 얼마입니까?

Question

n 및 n 양의 정수 배열을 사용하면 삼각형을 만들 수없는 세 개의 숫자를 선택할 수있는 방법의 수를 필요로합니다.

예 :

3 
4 2 10 

답 : (JAVA에서)

1 

내 접근

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); 

내 알고리즘 :

목록을 정렬 한 후 나는 그럴 생각합니다 모든 숫자가 arr[i]이되도록 arr[i]>=arr[j]+arr[k]과 같은 삼각형이 나타나지 않는 경우, ying을 클릭하십시오.

그러나이 솔루션의 경우 timed-out이 표시됩니다. 누구든지이 문제에 대한 더 나은 접근법을 제안 할 수 있습니까?

Answer 1

적절한 의사 코드가 될 것이다 : I 3 개 후 동일한 값으로 입력이 없을 것으로 가정

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 

. 그러한 가능성이 있으면 불필요한 값을 제거하십시오.

각 루프에 삼각형이 추가되었는지 확인해야합니다. 그렇지 않으면이 루프를 중단하십시오.

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을 증가 할 때마다, 우리는 전체 시간 복잡도 O(n^2)을 유지하는 데 도움이 k의 값을 재설정 할 필요가 없습니다 것을 알 수

//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;