Triangle Construction (ICPC)

题目连结

这次 ICPC 中的第 M 题，真的有点麻烦在 test24 给了 67000 个输入值

因为还在準备期末考，
这里只会先简单的讲，有兴趣可以上 Codeforces 去练习，或加入群组来讨论喔!!

==> 群组连结

解题思绪

简单来说，一个三角形要按题目组成只会有以下两种情况：

一边提供 2 个点(最多的一边)，剩下的提供 1 个点三边各提供 1 个点

而第二点的情况只有在刚好三边以上都是 1 才会用到

我们也可以 将全部的点加起来 / 3
虽然有点投机，但也不是真的再乱来
当主要的点（最多点的边）被扣除后小于 总和 / 3，这时我们就知道点都是他在提供
且同一边无法组成三角形

所以即可以得到以下结论：

如果点平均分散 → 总和除以三如果点只集中在一边 → 总和扣掉主要边

程式码

#include <iostream>#include <vector>#include <algorithm>#include <cmath>#define ll long longusing namespace std;/* * 题目: Triangle Construction * 题目来源: Codeforces (ICPC M) * 题目连结: https://codeforces.com/contest/1906/problem/M * 解题者: 神李绫华的狗 * 使用语言: C++ * 解题关键: 看上天，有没有要让你想到 */int main(int argc, char const *argv[]){    int n;    cin >> n;    vector<ll> v;    ll x;    ll ans = 0;    for (int i = 0; i < n; i++)    {        cin >> x;        ans += x;        v.push_back(x);    }    sort(v.begin(), v.end());    ans = min(ans / 3, ans - v[n - 1]);    cout << ans << endl;    return 0;}