代码丑陋,见谅。
思路:
先利用桶排序,将这些木棒的长度作为数组的下标,和这个长度一样的木棒计数。
再找出最大的长度,并判断这个长度中的数量是否超过两个,再找是否存在两个数的和是这个最大的长度,如果是,就计数。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const int mod=1e9+7;
ll num[N],cnt=0,s[N], n,m=0;
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
void cheak(int k)
{
for(int i=k-1;i>=1;i--){
if(s[i]&&s[k-i])
{
cnt++;
}
}
cnt%=mod;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>num[i],s[num[i]]++,m=max(m,num[i]);
for(int i=1;i<=m;i++)
{
if(s[i]>=2&&i>=2){
cheak(i);
}
}
printf("%lld\n",cnt);
return 0;
}