题解 | #木棍游戏#

木棍游戏

https://ac.nowcoder.com/acm/contest/11220/C

题意: 给出一些互不相同的木棍，选择其中的一些木棍。问能够拼凑出的三角形中最大的面积是多少。若不能拼出任何三角形，输出 $- 1$ 。

制约: $3 \le n \le 8, 1 \le a \le 10^3 \in \{A\}$

前置知识：三斜求积（海伦公式）。

p = \dfrac{a + b + c}{2}\\ \quad\\ S = \sqrt{p \times (p - a) \times (p - b) \times (p - c)}

数据较小，直接暴搜。

CPP代码

#include <bits/stdc++.h>
using namespace std;

int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int n;
  std::cin >> n;
  std::vector<int> A(n);

  for (auto &i : A) {
    std::cin >> i;
  }

  double ans = 0.0;

  std::function<void(int, int, int, int)> DFS = 
[&](int a, int b, int c, int id) {

    if (a && b && c && a + b > c && a + c > b && b + c > a) {
      double p = a + b + c;
      p /= 2.;
      ans = std::max(ans, std::sqrt(p * (p - a) * (p - b) * (p - c)));
    }

    if (id > n) {
      return;
    }

    DFS(a, b, c + A[id], id + 1);
    DFS(a + A[id], b, c, id + 1);
    DFS(a, b + A[id], c, id + 1);
    DFS(a, b, c, id + 1);
  };

  DFS(0, 0, 0, 0);

  if (ans == 0) {
    std::cout << -1;
  } else {
    std::cout << std::fixed << std::setprecision(1) << ans;
  }

  return 0 ^ 0;
}

bonus: 如果需要使用全部的木棍，该怎么处理？去洛谷看看这个题目

全部评论

推荐最新楼层

不愿透露姓名的神秘牛友

07-07 13:35

ChatGPT-5代考，竟然真能骗过字节面试官啊

虽然不怎么光彩，经过这件事，可能我真的要去认同“面试八股文早该淘汰！不会用AI作弊的程序员=新时代文盲！”这句话了

HellowordX：Ai的出现是解放劳动力的，不是用来破坏公平竞争环境的，这样下去，轻则取消所有线上面试，严重了会影响整个行业对所有人产生影响，企业会拉高入职考核各种离谱考核会层出不穷

你找工作的时候用AI吗？

点赞评论收藏

不愿透露姓名的神秘牛友

昨天 12:31

我从来没想过我会出轨

以前小时候我最痛恨出轨、偷情的人，无论男女，为什么会出轨？现在我成了自己最讨厌的人，没想到分享的东西在牛客会被这么多人看，大家的评价都很中肯，我也认同，想过一一回复，但我还是收声了，我想我应该说说这件事，这件事一直压在我心里，是个很大的心结，上面说了人为什么出轨，我大概能明白了。我们大一下半年开始恋爱，开始恋爱，我给出了我铭记3年的承诺，我对她好一辈子，我永远不会背叛，我责任心太重，我觉得跟了我，我就要照顾她一辈子，我们在一起3年我都没有碰过她，她说往东我就往东，她说什么我做什么，她要我干什么，我就干什么！在学校很美好，中途也出过一些小插曲，比如男闺蜜、男闺蜜2号等等等。但我都强迫她改掉了，我...

牛客刘北：两个缺爱的人是没有办法好好在一起的，但世界上哪有什么是非对错？你后悔你们在一起了，但是刚刚在一起的美好也是真的呀，因为其他人的出现，你开始想要了最开始的自己，你的确对不起自己，21岁的你望高物远，你完全可以不谈恋爱，去过你想要的生活，你向往自由，在一起之后，你要想的不是一个人，而是两个人，你不是变心了，就像你说的，你受够了，你不想包容了，冷静几天是你最优的选择，爱人先爱己。

社会教会你的第一课

点赞评论收藏