java - 有多少种方法不能构成三角形？

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

我的算法:

对列表排序后，我试图找到所有小于 arr[i] 的数字，这样 arr[i]>=arr[j]+arr[k]，在这种情况下三角形不会形成。

但是我正在为这个解决方案超时。谁能建议更好的方法来解决这个问题？

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 个相同值的输入。如果有这种可能性，请删除不必要的值。

在每个循环中，您应该检查是否添加了任何三角形。如果不是，则打破此循环。