[AtCoder] ARC 004 B – 2点間距離の最大と最小 ( Maximum and Minimum )

2020年9月18日2020年12月13日

問題

方針

最大値は辺の長さの総和となります。最小値は座標で考えると難しいので、図形として考えます。辺の長さを \( a < b < c \) とすると、\( c < a + b \) のとき三角形を作成することができます。したがって、辺の総和を \( s \) 、最長辺を \( d \) とすると、\( d \leq s – d \) のとき最小値は \( 0 \) となります。つぎに、\( d > s – d \) のとき、最長辺を始点と終点として折り返すことで、\( s – d \) が最小値となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    ll d[N - 1];
    ll sum = 0;
    ll v = 0;
    for (int i = 0; i < N; i++) {
        cin >> d[i];
        sum += d[i];
        v = max(v, d[i]);
    }
    sum -= v;
    cout << sum + v << "\n";
    cout << ((v <= sum) ? 0 : v - sum) << "\n";
    return 0;
}