点击打开链接
题意:给定一个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;
}
分享到:
相关推荐
资源分类:Python库 所属语言:Python 资源全名:Flask-Triangle-joeflack4-0.5.6.zip 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
Largest-Triangle-Three-Buckets 算法的 Javascript 实现 从的包含算法的稍微修改。 这个 repo 的目的是简单地包含没有 flot 插件的算法。
开源项目-esimov-triangle.zip,▲ Triangle - Convert images to computer art with Go.
Hello-Triangle-01.zip
前端大厂最新面试题-triangle
git-like-cli.zip,git-like cli是一个基于java注释的框架,用于解析git-like命令行结构。
用java语言实现数学中所学的杨辉三角,该算法简单
sierpinski triangle MATLAB Code
链接OpenGL库,绘制一个简单的图形,比如三角形和正方形
triangle - 使用delaunay三角网将图像转换为计算机艺术
gl-triangle-strip-indexer 创建能够传递给三角形条状网格的 WebGL 元素数组的类型化数组。 var createIndices = require ( 'gl-triangle-strip-indexer' ) var createBuffer = require ( 'gl-buffer' ) var ...
thomas法求解对称三角线性方程组,简单高效
用OpenGL實現的各種三角函數分段顯示,初學OpenGL所寫的代碼。
HELLO:react-black-triangle(和 )的版本为v0.1-如果您发现此代码很简洁,可以让我知道您想在哪里查看更多文档,从而使它变得更好! react-black-triangle为您提供直接构建基于React的应用程序所需的代码和约定。...
matlab循环读图的代码目录 描述 逐顶点三角形计数 我们将逐步实现共享内存实现,以计算无向,未加权图G(V,E)中与每个节点相邻的三角形的数量,其中V是n个节点的集合,E是集合节点之间m个边的数量。...
AD模块PCF8591 DA输出三角波(单片机的编程)
Fitbit-Clock-Triangle:Fitbit时钟面
手写笔三角形发生器使用 Stylus 生成 CSS 三角形的小...用法 triangle(width, height, direction, color) .make-me-a-triangle-babytriangle(10px, 10px, 'bottom', #000)新产品经理 npm install stylus-triangle谢谢
OpenGL-4.6-Hello-Triangle:使用着色器的著名OpenGL“ Hello Triangle”。 它使用OpenGL 4.5功能,称为直接状态访问
Acute-Triangle:带有拼图扭曲的子弹地狱射手