Triangle Construction (ICPC)

題目連結

• 這次 ICPC 中的第 M 題，真的有點麻煩在 test24 給了 67000 個輸入值

因為還在準備期末考，
這裡只會先簡單的講，有興趣可以上 Codeforces 去練習，或加入群組來討論喔!!

==> 群組連結

解題思緒

簡單來說，一個三角形要按題目組成只會有以下兩種情況：

1. 一邊提供 2 個點(最多的一邊)，剩下的提供 1 個點
2. 三邊各提供 1 個點

而第二點的情況只有在剛好三邊以上都是 1 才會用到

我們也可以 將全部的點加起來 / 3
雖然有點投機，但也不是真的再亂來
當主要的點（最多點的邊）被扣除後小於 總和 / 3，這時我們就知道點都是他在提供
且同一邊無法組成三角形

所以即可以得到以下結論：

• 如果點平均分散 → 總和除以三
• 如果點只集中在一邊 → 總和扣掉主要邊

程式碼

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define ll long long

using 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;
}