2018暑期SICNU-ACM组集训报告（9）

题目：
Triangles
File: triangulos.[c|cpp|java]
You will be given N points on a circle. You must write a program to determine how many distinct
equilateral triangles can be constructed using the given points as vertices.
The figure below illustrates an example: (a) shows a set of points, determined by the lengths of
the circular arcs that have adjacent points as extremes; and (b) shows the two triangles which can be
built with these points.

image.png

Input
The first line of the input contains an integer N, the number of points given. The second line contains
N integers Xi
, representing the lengths of the circular arcs between two consecutive points in the
circle: for 1 ≤ i ≤ (N − 1), Xi represents the length of the arc between between points i and i + 1;
XN represents the length of the arc between points N and 1.
Output
Your program must output a single line, containing a single integer, the number of distinct equilateral
triangles that can be constructed using the given points as vertices.
Restrictions
• 3 ≤ N ≤ 105
• 1 ≤ Xi ≤ 103
, for 1 ≤ i ≤ N
Examples
Input
8
4 2 4 2 2 6 2 2
Output
2
Input
6
3 4 2 1 5 3
Output
1

原题链接：https://odzkskevi.qnssl.com/1627a677139fc8e306696b4e41953e0f?v=1533137884 //Problem F

题意：圆上N个点把弧长分为N条，问能构成几个等边三角形

解题思路：一来就打算用弧长算出边长再比较的我是真的思路清奇，弧长相等即可。
一开始过于复杂度太高超时，用前缀和和二分算法优化了；
但直接弧长后卡在第4组测试数据；
这是一个圆，是成圈圈的，不是只能到头，所以我判定两次之后再把答案整除三即可得到正确答案。

AC代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=10000005;
int a[maxn];
ll pre[maxn*2];
 
int main()
{
    int n,i,j,k;
    cin>>n;
    ll sum=0;
    for(i=0;i<n;i++)
    {
        
        cin>>a[i],sum+=a[i];
        a[i+n]=a[i];
    }
    pre[0]=a[0];
    for(i=1;i<2*n;i++)
    pre[i]+=pre[i-1]+a[i];
    if(sum%3)
    {
        cout<<"0"<<endl;
        return 0;
    }
    ll t=sum/3,s=0,temp;
    for(i=0;i<n;i++)
    {
        ll c;
        if(i)
            c=pre[i-1]+t,temp=i-1;
        else
            c=t,temp=i;

        bool flag=0;
        int x=lower_bound(pre,pre+2*n,c)-pre;       
        if(x>=i+n)
            flag=1;
        
        if(flag)
            continue;

        c=pre[x]+t;temp=x;
        x=lower_bound(pre,pre+2*n,c)-pre;

        if(x>=i+n)
            flag=1;
        if(flag)
            continue;
        c=pre[x]+t;temp=x;
        x=lower_bound(pre,pre+2*n,c)-pre;

        if(x>=i+n)
            flag=1;
        if(flag)
            continue;
        if(!flag)
            s++;
    }
    cout<<s/3;
}