c++ - 对于这个 Codeforces 问题，有没有比仅仅使用蛮力更好的解决算法？

Question

给你一个数组 a1,a2,…,an。

在一次操作中，您可以选择两个元素 ai 和 aj (i≠j) 并将它们中的每一个减一。

您需要检查是否可以使所有元素都等于零。

以下链接 https://codeforces.com/contest/1201/problem/B

标签： c++

Answer 1

我认为检查总和是否偶数并且没有元素超过总和的一半就足够了。将 C++17 与参数包扩展和折叠表达式一起使用，这是一个简短的片段：

template<typename ...Ts>
bool check(Ts... an) {
    const auto sum = (an + ...);
    const auto max = std::max({an...});
    return sum % 2 == 0 && max <= sum / 2;
}

您必须一步一步减少两个元素。这意味着总和必须可以被二除。

使所有元素为零的一种算法是减少最大元素和第二个最大元素。对于 max 元素的每次减少，您都需要另一个可以减少的元素。只要最大元素不超过总和的一半，它就可以工作。