组装三角形

[编程题]组装三角形

热度指数：5742 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛手里有N根木棒,分别编号为1~N,现在他从N根里想取出三根木棒，使得三根木棒构成一个三角形,你能计算出牛牛有多少种取法吗?(考虑两种取法中使用的木棒编号有一个不一样就认为是不同的取法)。

输入描述:

首先输入一个正整数N，接下来的一行共有N个正整数表示每个木棒的长度。

N ≤ 50, 木棒的长度 ≤ 10000.

输出描述:

输出一个整数表示方法数。

示例1

输入

5
1 2 3 4 5

输出

算法知识视频讲解

三大爷的剑

尺取办法

package main
import (
    "fmt"
    "sort"
)

func main() {
    var arr []int 
    var count int
    fmt.Scanln(&count)
    
    if count <  3 {
        fmt.Println(0)
        return
    }
    for i := 0; i < count; i++ {
        var num int 
        fmt.Scanf("%d", &num)
        arr = append(arr, num)
    }
    sort.Ints(arr)
    // 尺取
    ans := 0
    for i := 0; i < len(arr) - 2; i ++ {
        l,r := i + 1, i + 2
        
        for r < len(arr) {
            if r == l {
                r ++
                continue
            }
             // 任意两边和大于另一个边
            abL := arr[i] + arr[l]
            if abL > arr[r]  {
                mostLessRight := r
                for mostLessRight < len(arr) && arr[mostLessRight] < abL {
                    mostLessRight ++
                }
                
                ans += mostLessRight - r
                l ++
            }else {
                l ++
            }
        }
    }
    fmt.Println(ans)   
}

发表于 2021-09-05 00:45:39 回复(0)