欢迎访问 生活随笔！
TAG聚合

生活随笔

当前位置： 首页 > 编程资源 > 编程问答 >内容正文

编程问答

NYOJ 982 Triangle Counting （数学题）

发布时间：2025/3/16 编程问答 40 豆豆
生活随笔 收集整理的这篇文章主要介绍了 NYOJ 982 Triangle Counting （数学题） 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

Triangle Counting

时间限制：1000 ms  |  内存限制：65535 KB 描述
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<stdio.h> 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; }

与50位技术专家面对面20年技术见证，附赠技术全景图

总结

以上是生活随笔为你收集整理的NYOJ 982 Triangle Counting （数学题）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。