首页 > 代码库 > UVA 11401 - Triangle Counting（数论+计数问题）
UVA 11401 - Triangle Counting（数论+计数问题）
题目链接：11401 - Triangle Counting
题意：有1,2,3....n的边，求最多能组成的三角形个数。
思路：利用三角形不等式，设最大边为x,那么y + z > x 得 x - y < z < x
然后y取取值，可以从1取到x - 1，y为n时候，有n - 1个解，那么总和为0 + 1 + 2 +...+ (x - 2) = (x - 1) * ( x- 2) / 2;
然后扣除掉重复的y = z的情况，在y > x / 2时，每个y取值会出现一次y = z.
然后在扣除掉一半y,z交换的相同情况。最后就是答案
得到递推式ans[i] = ans[i - 1] + ((i - 1) * (i - 2) / 2 - (i - 1) / 2) / 2;
代码：
#include <stdio.h>
#include <string.h>
const int N = 1000005;
int n;
long long ans[N];
int main() {
ans[3] = 0;
for (long long i = 4; i <= 1000000; i++) {
ans[i] = ans[i - 1] + ((i - 1) * (i - 2) / 2 - (i - 1) / 2) / 2;
}
while (~scanf("%d", &n) && n >= 3) {
printf("%lld\n", ans[n]);
}
return 0;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。