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

<script type="text/java script">

<script type="text/java script">BAIDU_CLB_fillSlot("771048");

点击复制链接 与好友分享! 回本站首页

<script> function copyToClipBoard(){ var clipBoardContent=document.title + '\r\n' + document.location; clipBoardContent+='\r\n'; window.clipboardData.setData("Text",clipBoardContent); alert("恭喜您！复制成功"); }

分享到： 更多

<script type="text/java script" id="bdshare_js" data="type=tools&uid=12732"> <script type="text/java script" id="bdshell_js"> <script type="text/java script"> var bds_config = {'snsKey':{'tsina':'2386826374','tqq':'5e544a8fdea646c5a5f3967871346eb8'}}; document.getElementById("bdshell_js").src = "http://bdimg.share.baidu.com/static/js/shell_v2.js cdnversion=" + Math.ceil(new Date()/3600000)

您对本文章有什么意见或着疑问吗？请到 论坛讨论您的关注和建议是我们前行的参考和动力

上一篇： C 基础数据结构---队列 ADT

下一篇： C语言单元测试

相关文章

<script type="text/java script">BAIDU_CLB_fillSlot("182716");

<script type="text/java script">BAIDU_CLB_fillSlot("517916");

图文推荐

<script type="text/java script">BAIDU_CLB_fillSlot("771057");