首页 > 试题广场 >

三角谜题

[编程题]三角谜题

热度指数：2189 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 对于给定的 $n$ 种长度的棍子，第 $i$ 种棍子的长度为 $l_i$ ，有 $a_i$ 根。从中任选三根，能组成的等腰三角形的面积最大值为多少？
$\hspace{15pt}$ 如果无法组成等腰三角形，则直接输出 $-1$ 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数  代表棍子的种类。
此后  行，第  行输入两个整数  代表第  种棍子的长度和数量。

除此之外，保证单个测试文件的  之和不超过  。

输出描述:

在一行上输出一个实数，代表组成的最大等腰三角形的面积。如果无法组成等腰三角形，则直接输出  。

由于实数的计算存在误差，当误差的量级不超过  时，您的答案都将被接受。具体来说，设您的答案为  ，标准答案为  ，当且仅当  时，您的答案将被接受。

示例1

输入

输出

3.89711431702997391060
-1

说明

对于第一组测试数据，可以构造  为底、 为腰的三角形，面积  ；也可以构造  为底、 为腰的三角形，面积  。显然，后者更大。

备注:

本题数据量较大，我们建议您使用较快的读入方式。

算法知识视频讲解

Python3

you_config

答案应该是对的，但是提交超时通不过，可以参考我的写法，

from collections import defaultdict
import math
T = input() # 组数
for _ in range(int(T)):
    n = input()
    t = defaultdict(int)  # 字典保存每组不同长度的棍子及其数量
    for i in range(int(n)):
        s = input().split()
        t[int(s[0])] += int(s[1])
    area = -1  # 面积，初始为-1
    for x in t:
        if t[x] >= 2: # 遍历字典，取两根相同长度的棍子，
            t[x] -= 2 # 取两根棍子，数量减2
            a = x # a为三角形的腰
            for y in t:
                if 0 < y < a*2 and t[y] > 0:
                    b = y # b为三角形的底边
                    area = max(area, math.sqrt(a**2-(b/2)**2)*b/2) # 计算面积
            t[x] += 2 # 棍子用完之后要加回来
    print(area)

发表于 2025-04-25 01:41:16 回复(0)

Python3

是我的神的靓仔很自信

为什么不能通过，明明代码是正确的

import math

def cal(arr1,arr2):

arr=[]

#print(arr1,arr2)

for i,j in zip(arr1,arr2):

arr.append([i,j])

arr.sort(reverse=True)

area=-1

for i in range(len(arr)):

if arr[i][1]>=2:

y=arr[i][0]

arrx=[]

if i>=1:

x=arr[i-1][0]

if x<2*y:

arrx.append(x)

if arr[i][1]>2:

arrx.append(arr[i][0])

if i+1<len(arr):

arrx.append(arr[i+1][0])

for x in arrx:

h2=y**2-(x/2)**2

#temp= math.sqrt((h2/4)*((x)**2))

s = (y+y+x) / 2

temp=math.sqrt(s * (s - y) * (s - y) * (s - x))

#temp=h*x/2

if area<temp:

area=temp

if area>-1:

return area

return -1

while True:

try:

n=int(input())

for _ in range(n):

k=int(input())

arr1,arr2=[],[]

for i in range(k):

l,a=list(map(int,input().split()))

if l in arr1:

idx=arr1.index(l)

arr2[idx]=arr2[idx]+a

else:

arr1.append(l)

arr2.append(a)

res=cal(arr1,arr2)

print(res)

except:

break

发表于 2025-04-09 17:50:09 回复(0)

Java

牛客279643016号

解题思路:

1. 按照长度逆序排序，key：木棍长度，value：数量

2. 遍历value集合，找到第一个数量大于1的木棍 i 作为腰

3. 从0开始遍历key，一直到第二步的 i+1 个，找到第一个符合等腰三角形的组合，就是最大值

代码参考如下：（Math.sqrt方法精度只能到15或16，本题精确到了20，于是自定义了sqrt方法）

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int total = in.nextInt();
        BigDecimal[] result = new BigDecimal[total];
        for (int i = 0; i < total; i++) {
            int typeCount = in.nextInt();
            int[][] lenAndNum = new int[typeCount][2];
            for (int j = 0; j < typeCount; j++) {
                lenAndNum[j][0] = in.nextInt();
                lenAndNum[j][1] = in.nextInt();
            }
            result[i] = getResult(lenAndNum);
        }
        for (BigDecimal d : result) {
            System.out.println(d);
        }
    }

    public static BigDecimal getResult(int[][] lenAndNum) {
        Map<BigDecimal, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < lenAndNum.length; i++) {
            BigDecimal len  = BigDecimal.valueOf(lenAndNum[i][0]);
            int num = lenAndNum[i][1];
            if (map.containsKey(len)) {
                map.put(len, map.get(len) + num);
            } else {
                map.put(len, num);
            }
        }
        map = map.entrySet().stream().sorted(Collections.reverseOrder(
                Map.Entry.comparingByKey())).collect(
                  Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (l1, l2)->l1,
                                   LinkedHashMap::new));
        List<BigDecimal> keyList = new LinkedList<>();
        List<Integer> valueList = new LinkedList<>();
        for (Map.Entry<BigDecimal, Integer> item : map.entrySet()) {
            keyList.add(item.getKey());
            valueList.add(item.getValue());
        }
        for (int i = 0; i < valueList.size(); i++) {
            Integer num = valueList.get(i);
            if (num >= 2) {
                for (int j = 0; j < Math.min(i + 1, valueList.size()); j++) {
                    if (num > 2) {
                        BigDecimal result = cal(keyList.get(i), keyList.get(j));
                        if (result.compareTo(BigDecimal.ZERO) > 0) {
                            return result;
                        }
                    }
                    if (num == 2 && i != j) {
                        BigDecimal result = cal(keyList.get(i), keyList.get(j));
                        if (result.compareTo(BigDecimal.ZERO) > 0) {
                            return result;
                        }
                    }
                }
            }
        }
        return BigDecimal.valueOf(-1);
    }

    public static BigDecimal cal(BigDecimal yao, BigDecimal di) {
        if (yao.add(yao).compareTo(di) < 0) {
            return new BigDecimal(-1);
        }
        BigDecimal halfDi = di.divide(BigDecimal.valueOf(2), 20, RoundingMode.HALF_UP);
        BigDecimal sqrtValue = yao.multiply(yao).subtract(halfDi.multiply(
                                   halfDi));
        BigDecimal gao = sqrt(sqrtValue, 20);
        return di.multiply(gao).divide(BigDecimal.valueOf(2), 20,
                                       RoundingMode.HALF_UP);
    }

    public static BigDecimal sqrt(BigDecimal num, int precision) {
        // 负数不能开平方
        if (num.compareTo(BigDecimal.ZERO) < 0) {
            throw new ArithmeticException("不能对负数开平方");
        }
        MathContext context = new MathContext(precision, RoundingMode.HALF_UP);
        BigDecimal guess = num.divide(BigDecimal.valueOf(2), context);
        BigDecimal tolerance = BigDecimal.ONE.scaleByPowerOfTen(-precision);
        while (true) {
            BigDecimal nextGuess = guess.add(num.divide(guess,
                                             context)).divide(BigDecimal.valueOf(2), context);
            if (nextGuess.subtract(guess).abs().compareTo(tolerance) <= 0) {
                return nextGuess;
            }
            guess = nextGuess;
        }
    }

发表于 2025-03-22 16:24:10 回复(0)

Rust

PeterFu

遍历所有的底边和侧边，求最大面积即可。但不知道为啥超时了。

use std::collections::HashMap;
use std::io::*;

fn solve(group: HashMap<usize, usize>) {
    let congruent_group: HashMap<usize, usize> = group
        .iter()
        .filter(|(_, &v)| v >= 2)
        .map(|(k, v)| (*k, *v))
        .collect();
    if congruent_group.is_empty() {
        println!("-1");
        return;
    }
    let mut max_area = 0.0f64;
    let mut found = false;
    for base_side in group.iter() {
        let (&length_b, _) = base_side;
        for congruent_side in congruent_group.iter() {
            let (&length_c, &count_c) = congruent_side;
            if 2 * length_c <= length_b {
                continue;
            }
            if length_b != length_c && count_c < 2 {
                continue;
            }
            if length_b == length_c && count_c < 3 {
                continue;
            }
            found = true;
            let area = (length_b as f64)
                * (length_c.pow(2) as f64 - length_b.pow(2) as f64 / 4.0).sqrt()
                / 2.0;
            max_area = max_area.max(area);
        }
    }
    if found {
        println!("{}", max_area);
    } else {
        println!("-1");
    }
}
fn main() {
    let stdin = stdin();
    let mut line = String::new();
    stdin.read_line(&mut line).unwrap();
    line.pop();
    let t: usize = line.parse().unwrap();
    for _ in 0..t {
        line.clear();
        stdin.read_line(&mut line).unwrap();
        line.pop();
        let n: usize = line.parse().unwrap();
        let lines: Vec<(usize, usize)> = stdin
            .lock()
            .lines()
            .take(n)
            .map(|l| {
                let l = l.unwrap();
                let mut it = l.split_whitespace();
                (
                    it.next().unwrap().parse().unwrap(),
                    it.next().unwrap().parse().unwrap(),
                )
            })
            .collect();
        let group = lines.iter().fold(HashMap::new(), |mut acc, &(a, b)| {
            acc.entry(a).and_modify(|x| *x += b).or_insert(b);
            acc
        });
        solve(group);
    }
}

发表于 2025-03-06 11:34:49 回复(0)

提交观点

问题信息

难度：

4条回答 24收藏 114浏览

三角谜题

输入描述:

输出描述:

输入

输出

说明

备注:

问题信息

热门推荐

相关试题