`
从此醉
  • 浏览: 1034725 次
  • 性别: Icon_minigender_1
  • 来自: US
社区版块
存档分类
最新评论

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个解。总的就是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;
}



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics