暴力枚举三角

这是暴力枚举类型的一道算法题

妖梦拼木棒

题目描述

有n根木棒,现在从中选4根,想要组成一个正三角形,问有几种选法？

输入格式

第一行一个整数n;第二行往下n 行,每行一个整数,代表木棒的长度

解释

1.先统计最小的ai和最大的ai,和每个长度木棒各有几根,即bi;
2.4根木棒中,必须有两根木棒长度相等且不是最短的;
3.从第二小的开始枚举(因为最小的不能通过别的木棒合成),看此木棒是不是有两根,没有就下一个;
4.通过i/2和bi来确定用来合成的第一根木棒j,通过i-j确定另一根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<fstream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<iomanip>
using namespace std;
int n,b[5010],a[1000010],minn=1e9,maxx;
long long ans;
const int mod=1e9+7;
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];//输入
        minn=min(minn,a[i]);//找出最小的ai
        maxx=max(maxx,a[i]);//找出最大的ai
        b[a[i]]++;//数组计数
    }
    for(int i=minn+1; i<=maxx; i++)//这里从最小量+1开始枚举，是因为最小量不可能有两个比它更小的两组成
    {
        if(b[i]>1)//如果这个数字有一个以上
            for(int j=minn; j<=i/2; j++)//开始枚举
                if(b[j]>=1&&b[i-j]>=1)//如果他可以被两个比他小的两组成//一个是比i一半还小的j,另一个通过i-j定位能不能组成
                {
                    if(j*2!=i)ans=(ans+(b[i]*(b[i]-1)/2)*b[j]*b[i-j]%mod)%mod;//统计
                    else if(b[j]>1)ans=(ans+((b[i]*(b[i]-1)/2)*(b[j]*(b[j]-1)/2)%mod)%mod)%mod;//统计
                }
    }
    cout<<ans%mod;//输出
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
import java.util.Scanner;

public class Main {
    
    static Scanner sc;
    static int MO = 1000000007;
    static int n;//n个数
    static int[] num;//存储每个数字出现的个数
    static int max = 0;//存储木棍长度最大值
    static int temp;//临时变量存储sc.nextInt()
    static int sum = 0;
    
    
    public static void main(String[] args) {
        //初始化
        sc = new Scanner(System.in);
        n = sc.nextInt();
        num = new int[5001];
        
        for (int i = 0; i < n; i++) {
            temp = sc.nextInt();
            if (temp > max) {
                max = temp;
            }
            num[temp]++;
        }
        
        /**
         * 易知:a=b=c+d
         * 一、即先取两支一样长且长度为i的木棍
         * 二、再从比i长度小的木棍取两支木棍j、i-j
         *    ①j == i-j,从相同长度木堆取两个
         *    ②j != i-j,从不同长度两个木堆分别取一个
         *    ③为避免取重复,应控制 j < i - j,即j < i / 2
         */
        
        //如果从长度为1的木堆开始取两个,很明显没有这种情况,因此从长度为2的木堆开始取
        for (int i = 2; i <= max; i++) {
            if (num[i] >= 2) {//此木堆超过两支木棍
                 int fs = C(num[i], 2) % MO;
                //取完两支长短一样的木棍后,开始取另外两根长度未知的
                for (int j = 1; j <= i / 2; j++) {
                    //1、长度一样;那么就在同一木堆取两个
                    if (j == i - j && num[j] >= 2) {
                        sum = (sum + fs * C(num[j], 2)) % MO;
                    }
                    //2、长度不一样;那么就在两个不同木堆分别取一个
                    if (j != i - j && num[j] >= 1 && num[i-j] >= 1) {
                        sum = (sum + fs * C(num[j], 1) * C(num[i-j], 1)) % MO;
                    }
                }
            }
        }
        
        System.out.println(sum);
    }

    // 求组合数
    // 要么C(n,1) 要么C(n,2)
    public static int C(int k, int r) {
        if (r == 1) {
            return k % MO;
        }
        return (k * (k - 1) / 2) % MO;
    }
}