NYOJ 982 Triangle Counting （數學題）

Triangle Counting

描述

You are given n rods of length 1, 2…, n. You have to pick any 3 of them and build a triangle. How many distinct triangles can you make? Note that, two triangles will be considered different if they have at least 1 pair of arms with different length.

輸入

The input for each case will have only a single positive integer n(1<=n<=1000000). The end of input will be indicated by a case with n<1. This case should not be processed.

輸出

For each test case, print the number of distinct triangles you can make.

樣例輸入

5
8
0

樣例輸出

3
22

題目大意：給出n條線段，長度為1-n，問有多少種方法可以從這n條線段中取出3條不同的線段，使得以它們為三邊長可以組成三角形。

分析：首先想到的方法就是三重循環枚舉，但是時間復雜度為O(n^3)，肯定超時。數據規模即使是O(n^2)時間的算法都很難承受，所以要進行數學分析。

設最大邊長為x的三角形有C(x)個，另外兩條邊長分別為y和z，根據三角不等式有y+z>x。所以z的范圍是x-y < z < x。

根據這個不等式，當y=1時x-1 < z < x,無解；y=2時有一個解（z=x-1）；y=3時有兩個解（z=x-1或者z=x-2）……直到y=x-1時有x-2個解。根據等差數列求和公式，一共有0+1+2+……+（x-3）+ （x-2） = (x-1)(x-2)/2個解。

可這並不是C(x)的正確值，因為上面的解包含了y=z的情況，而且每個三角形算了兩遍。所以要統計出y=z的情況。y的取值從x/2+1開始到x-1為止，一共有(x-1) - (x/2+1) + 1 = x/2 - 1個，但是我們不難發現，當x為奇數時，y的取值為x/2個；x為偶數時，y的取值為x/2-1個。所以為了避免討論x的奇偶性，我們把x/2-1寫成(x-1)/2就可以了，而且不影響正確結果。把這分解扣除，然後在除以2，即C(x)=((x-1)(x-2)/2 - (x-1)/2)/2;原題要求的是"最大邊長不超過n的三角形數目F(n)",則F(n)=C(1)+C(2)+…+C(n)。寫成遞推式就是F(n) = F(n-1) + C(n)。

#include
long long ans[1000005];
int main()
{
    ans[1] = ans[2] = ans[3] = 0;
    for(long long x = 4; x <= 1000000; x++)
        ans[x] = ans[x-1] + ((x-1)*(x-2)/2 - (x-1)/2) / 2;
    int n;
    while(~scanf("%d",&n))
    {
        if(n < 1) break;
        printf("%lld\n",ans[n]);
    }
    return 0;
}