c# - 优化(降低复杂性)。从 n 个边长计算锐角、直角和钝角三角形

Question

编辑 1:将约束中的 104 更改为 10^4。很抱歉弄错了。

问题陈述: 我们有 N 根棍子。第 i 根棍子的大小是 Ai。我们想知道从一根不同的棍子的每一边创建的不同类型的三角形的数量。计算锐角三角形、直角三角形和钝角三角形的个数。

输入格式: 第一行包含 N。 第二行包含 N 个整数。第 i 个数字表示 Ai。

约束:

For full score: 3≤N≤5000
For 40% score: 3≤N≤500

对于所有测试用例:

1≤A[i]≤10^4
A[i]<A[i+1] where 1≤i<N

输出格式: 打印3个整数:分别是锐角三角形、直角三角形和钝角三角形的个数。

我的解决方案: 我的代码在给定时间内运行小 n(~500)。它适用于大 n(~5000)，但我在 Online Judge 上收到超出时间限制的错误。

我的代码:我使用 C# 作为语言。我希望得到同样的解决方案。

using System;

namespace CodeStorm
{
    class CountingTriangles
    {
        public static double square(int x)
        {
            return Math.Pow(x, 2);
        }

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string[] A_temp = Console.ReadLine().Split(' ');
            int[] A = Array.ConvertAll(A_temp, Int32.Parse);

            int acute = 0, right = 0, obtuse = 0;
            for (int i = 0; i < n - 2; i++) 
            {
                for (int j = i + 1; j < n - 1; j++) 
                {
                    int k = j + 1;
                    while (k < n && A[i] + A[j] > A[k])
                    {
                        if (square(A[i]) + square(A[j]) == square(A[k]))
                        {
                            right++;
                        }
                        else if (square(A[i]) + square(A[j]) > square(A[k]))
                        {
                            acute++;
                        }
                        else
                        {
                            obtuse++;
                        }
                        k++;
                    }
                }
            }
            Console.WriteLine(acute + " " + right + " " + obtuse);
            Console.ReadLine();
        }
    }
}

https://ideone.com/zbQXE9

上面的代码完美运行并找到了可能的三角形

输入:

6    
2 3 9 10 12 15

输出:

2 1 4

可能的三角形是:

锐角三角形 10−12−15, 9−10−12

直角三角形 9−12−15

钝角三角形 2−9−10, 3−9−10, 3−10−12, 9−10−15

我想知道一个更有效的方法来解决这个问题，这样我就可以在给定的 n(~5000) 时间限制内执行它。 在我试图找到复杂性之后，我想到了 O(n^3)。我不擅长复杂的事情。我可能错了。我想要一种更有效的方法来解决这个问题。

Answer 1

您可以通过以下方式改进该方法:首先按长度对所有木棍进行排序。之后迭代每对棍子(即具有平方复杂度的双循环)。对于每一对执行 binary search在棍子阵列中找到从锐角三角形切换到直角三角形的位置(考虑到您预先选择的两个棍子，第三个棍子作为基础)。然后执行另一个二进制文件以找到从右到钝角三角形的切换位置。之后，您将不得不执行另一次二分查找，以找到第三根棍子太长以至于您无法与它形成有效三角形的位置。您将不得不处理另一种情况 - 如果没有直角三角形并且您从锐角直接切换到钝角(这可以通过添加一个 if 来完成)。

重要的是要注意三角形的类型是由与三角形最大边相对的角度决定的，因此在上面的算法中你应该只考虑边长大于两个预选的棍子(可以使用另一个二进制文件)。

总体而言，我提出的方法的复杂度为 O(N² * log(N))，渐近地优于您的算法。