uva 11401 - Triangle Counting

简介: 点击打开链接 题意:给定一个n表示有n个1~n的数,现在要从这里面选出3个不同的整数问可以组成三角形的个数 思路: 1 n的上限是10^6,O(n^2)以上的时间复杂度都无法满足要求 2 设最大的变长为x,另外两边的为y和z并且x y 和z是不同的,那么有y+z > x,因此就有x-y < z < x    根据这个不等式我们知道,y = 1时无解,y = 2时有1个解 ........  y = x-1式有x-2个解。

点击打开链接

题意:给定一个n表示有n个1~n的数,现在要从这里面选出3个不同的整数问可以组成三角形的个数

思路:

1 n的上限是10^6,O(n^2)以上的时间复杂度都无法满足要求

2 设最大的变长为x,另外两边的为y和z并且x y 和z是不同的,那么有y+z > x,因此就有x-y < z < x

   根据这个不等式我们知道,y = 1时无解,y = 2时有1个解 ........  y = x-1式有x-2个解。总的就是0+1+2.......+x-2 = (x-1)*(x-2)/2

3 但是上面的等式并不是正确的数值。因我上面的解包含了y = z的情况,而且每个三角形算了两遍,因为y和x的地位是等价的。我们怎么解决上面的问题呢?

   先解决y = z的情况吧,当y = z的时候x - z < z < x,那么就有x < 2z,有x/2 < z < x,因此满足的z个数有(x-1)-(x/2+1)

那么只要扣掉这些解,再除以2即可。

4 根据上面的推理分析,我们可以知道题目实际上要求的是“最大边长不超过n的三角形的个数”,因为最大变长的范围从3~n,枚举是不可能的。但是我们仔细分析,我们可以事先打好表,ans[n]表示最大边长不超过n的三角形的个数,那么ans[n] = ans[n-1] + [(x-1)*(x-2)/2 - (x-1)-(x/2+1)]/2

代码:

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long int64;
const int MAXN = 1000010;

int64 n , ans[MAXN];

int64 getVal(int64 x){
	return ((x-1)*(x-2)/2-(x-1)/2)/2;
}

void init(){
    ans[3] = 0;
    for(int64 i = 4 ; i < MAXN ; i++)
		ans[i] = ans[i-1]+getVal(i);
}

int main(){
	init();
    while(cin>>n && n >= 3)
		cout<<ans[n]<<endl;
	return 0;
}



目录
相关文章
UVa11296 - Counting Solutions to an Integral Equation(枚举技巧)
UVa11296 - Counting Solutions to an Integral Equation(枚举技巧)
61 0
LeetCode 70. Climbing Stairs
你正在爬楼梯。 它需要n步才能达到顶峰。 每次你可以爬1或2步。 您可以通过多少不同的方式登顶? 注意:给定n将是一个正整数。
72 0
LeetCode 70. Climbing Stairs
[LeetCode]--59. Spiral Matrix II
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order. For example, Given n = 3, You should return the following matrix: [ [ 1, 2, 3 ], [ 8, 9
1156 0
[LeetCode]--54. Spiral Matrix
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. For example, Given the following matrix: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9
960 0
[LeetCode]--70. Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? 这是一个很经典的爬楼梯问题,面试也会经常遇
1171 0
[LeetCode] Climbing Stairs
Note: If you feel unwilling to read the long codes, just take the idea with you. The codes are unnecessarily long due to the inconvenient handle of matrices.
721 0
leetcode 70 Climbing Stairs
 Climbing Stairs                       You are climbing a stair case. It takes n steps to reach to the top.
1139 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等