题解：CF1957A Stickogon

feicheng · 2024-04-28 18:03:42 · 题解

Description

给定 n 个小棍，第 i 个小棍的长度为 a_i，你需要用这些小棍拼出尽可能多的正多边形。拼出的正多边形需要满足如下两个条件：

1. 正多边形的每一条边都只有一根小棍。
2. 一根小棍只能用在一个正多边形上。

Solution

当 n<3 时答案为 0。

当 n\geq 3 时，我们记录每个长度出现的次数 l_i，则长度 i 可以拼出的最多多边形个数为 \left\lfloor\dfrac{l_i}{3}\right\rfloor，即全部拼成正三角形，最后一个视余数情况拼为正方形或正五边形。

Essential Code

constexpr int N = 110;

int n, ans, range;
int length[N];

template<typename Read, typename Print> inline void solve(Read& in, Print& out) {
  in >> n;
  ans = range = 0;
  std::memset(length, 0, sizeof length);
  for (int i = 1, temp; i <= n; ++i) {
    in >> temp;
    check_max(range, temp);// 维护最大的长度
    length[temp]++;
  }
  if (n <= 2) return out << 0 << '\n', void();
  for (int i = 1; i <= range; ++i) {
    ans += length[i] / 3;
  }
  out << ans << '\n';
}