热乎着，昨晚阿里这题真太绝了

前言

大家好，我是bigsai，好久不见甚是想念。

昨晚有个同学参加了阿里的笔试题，笔试完后同学说这次笔试感觉难，跟我说了其中一道题，我看了感觉还是挺有质量的，看着这个难度都是第二题，总共三题感觉还是有难度的(瑟瑟发抖)，想着还是和大家分享一下。

描述

一个正m边形，他想知道多边形中等腰锐角三角形的数量。(三角形的顶点要在多边形的顶点上) 不同的三角形的定义:两个三角形，只要有一个点不在同一个位置上就算做不同的三角形。

数据范围3-10^7

分析

昨天看到这个问题，觉得还是比较新颖，也有很多细节，但是刚拿到这个问题自己懵逼的画了好久也才想出来，这里给大家share一下。

瞎折腾

问题的描述很简单，边为n的正多边形有多少等腰锐角三角形。

遇到这种问题我们该怎么分析呢？当然是先画几个案例分析一下。

这么一看，你可能觉得好像没啥规律哇。

你可能对奇数的有点眉目:奇数的每个边直直的就是对应一个点，那么有多少条边就有多少个等腰锐角三角形？

但是这个显然是错误的，有可能以不同的顶点作为等腰锐角三角形它刚好是个等边三角形，这样就会出现重复，然后还有的底边可能并不是恰好是多边形的一个边，而是多边形多个边组成底边(参考上图的正6边型)。

并且从这来看奇数边和偶数边还是有点区别的：放正来看，奇数的是点对边，而偶数的是点对点，结构上有些区别，那么有可能奇偶在结果上是有点区别的。

上面都是一个懵懵懂懂的状态，咱们整理一下有用的信息：

• 正多边形，多少边就是多少个顶点
• 正多边形，有轴对称的特性，等腰锐角三角形，也有轴对称的特性。
• 等腰锐角三角形，腰有两个，而底边有一个，要么从底边考虑，要么从顶点考虑，这里底边如上面的正6边型甚至更多边型显然不容易考虑，但是各个顶点都是多边形的顶点，所以肯定从顶点考虑。算出一个顶点为等腰锐角顶角的所有三角形乘以顶点数量(如正五边形)然后减去重复(如正3、正6边形)的就是总结果了。
• 奇数偶数分开讨论。

偶数情况

我们先用偶数的情况分析，先不考虑重复情况(考虑太多脑子混淆)，将 图形摆一下成这样：

因为为正多边形，所以也就相当于各个顶点在圆上，这样更容易分析是不是锐角，这样的分析每个点，就很容易看出每个顶点对应多少个锐角了，正6、正8每个顶点都对应一个锐角，其实有的人可能已经看出规律了，就是在直角下方的线都能组成锐角。

为了更清晰的观察，看下面这个图更清晰：

其实就是计算直角下面的蓝色线的数量，这个直观一点是所有横线数量的一半(向下取整)，每个横线由两个点组成，我们计算一下：

总共n个点，去掉两个顶点和最底下单个点，n-2个点组成(n-2)/2的线。其中直角下面的占一半就是[(n-2)/2]/2=(n-2)/4个,然后乘以顶点数量n，那么在偶数情况不考虑重复所有等腰锐角三角形数量为：

total=n*((n-2)/4))

奇数情况

回了偶数分析，奇数也很简单，奇数顶点不变，底边固定，也就是找能够组成锐角三角形的边数。

对于横线数量，如果是偶数个没疑问下面是锐角(上面多个顶点所以角度比直角小)，而奇数个中间那条线同样也是锐角(如果去掉顶点才在中央),所以这种情况是横线数量的一半(向上取整)，我们计算一下：

总计n个点，一个顶点，n-1个点组成线。那么有(n-1)/2个线，其中组成锐角三角形的一半向上取整那就是(n-1)/2+1,然后乘以顶点数量n，那么在奇数情况不考虑重复所有等腰锐角三角形数量为：

total=n*(((n-1)/2+1)/2))

重复三角形

上面考虑了不重复的三角形的情况，那么重复的三角形该怎么考虑了，上面看到正三角形、正6边型都遇到等边三角形而导致重复计算。

而正5、正7好像没有重复的等边三角形。

我们认真分析一下：等腰锐角三角形三个顶点都在正多边形的边上，其实也在一个圆上，如果构成等边三角形，说明这三个顶点能够将空间均分分开(也就是顶点、圆可以均匀分成三份)。那么顶点数量 n必须是三的倍数才可以啊！

顶点数量n是3的倍数，那么具体重复了多少呢？

就是看这种等边三角形每个作为顶点，本来应该有n个，但是每种情况出现了三次，所以只考虑其中1/3作为顶点的等边三角形才不重复！所以我们要总次数去掉n的(2/3)。

那么总次数：

 total-=(n/3)*2;

具体代码

这里代码有个小坑，n是10^7,那么这个数量级会越界int范围，需要用long，但是输入有的人用int计算这么样代码：

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();

    long total;
    if(n%2==0)
       total=n*((n-2)/4);
    else
       total=n*(((n-1)/2+1)/2);
    if(n%3==0){
            total-=(n/3)*2;
    }
    System.out.println(total);
}

但是还是错了，有的人还不知道为啥，主要的原因是下面这两句越界了：

total=n*((n-2)/4);
total=n*(((n-1)/2+1)/2);

有人说我已经total设成total设成long为啥还是错的，因为赋值运算符是先计算右侧n*((n-2)/4)此时相当于这么一个流程:

int temp=n*((n-2)/4);
long total=temp;

因为计算的数值范围都是int，所以最后结果也是int已经越界，然后将越界的这个int结果赋值给long范围的total。

和这个很类似的还有：

 double a=3/2;
 System.out.println(a);

会输出1.0而不是1.5，如果想要正确计算那么要提前将计算的值转成double计算：

 double a=(double) 3/2;

同样这个问题正确的代码为：

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    long total;
    if(n%2==0)
      total=(long)n*((n-2)/4);
    else
      total=(long)n* (((n-1)/2+1)/2);
    if(n%3==0){
      total-=(n/3)*2;
    }
    System.out.println(total);
}

总结

这种数学题、或者找规律的题还是偶尔可能碰到，多会一题多长个经验！当前还是以积累为主。

大家一起加油，有需要的也欢迎一起打卡力扣。

我是bigsai，肝了一本数据结构与算法pdf和一本动态规划pdf