\(\color{#ff0000}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.5}}}}}\)

\(\color{#ff0000}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{#ff0000}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{#ff0000}{\text{Mình xin rút kinh nghiệm và chấn chỉnh bản thân nếu trong editorial có gì sai sót, và bạn có thể gửi feedback }}\) ở đây

\(\color{#300000}{\text{Hint 1 <Cày trâu> <Tham lam>}}\)

• Thử từng số nguyên \(X\), chắc chắn là \(0 \leq X \leq \underset{i \in [1..n]}{\Sigma}a_i\)

Chứng minh: Nếu \(X > \underset{i \in [1..n]}{\Sigma}a_i\) thì sau khi qua từng ải ta còn lại \(Y = X - \underset{i \in [1..n]}{\Sigma}a_i > 0\)

• Và tất nhiên để đạt lợi thế thì ta sẽ sử dụng áo vào \(a_i < k\) lớn nhất hoặc số \(a_j \geq k\) bất kì để được hiệu quả nhất

Chứng minh, nếu chọn một thằng \(a_t < M = max({a_1, a_2, \dots, a_n})\) thì mình chỉ được lợi một khoản nhỏ hơn vì \(max(0, a_t - k) \leq max(0, M - k)\)

\(\color{#300000}{\text{Hint 2 <Tham lam>}}\)

• Thay vì thử từng số, thì mình nhận thấy luôn là \(X = \underset{i \in [1..n]}{\Sigma}a_i - Y\) với \(Y = (0, a_j - k)\)

Vì \(X\) càng nhỏ nên \(Y\) phải càng lớn

Mà dựa vào nhận xét với \(a_i\) bất kì ta có \(max(0, a_i - k) \leq max(0, M - k)\) với \(M = max({a_1, a_2, \dots, a_n})\)

Nên ta có \(Y = max(0, M - k)\)

Kết quả của bài toán là giá trị \(X\) nhỏ nhất có thể lấy sau khi sài bộ giáp cho số có giá trị lớn nhất

\(\color{#009933}{\text{Preference AC Code }}\): Tham lam

\(^{^{\color{#7f5f3f}{\text{Complexity : }} O(n)\ \color{#7f5f3f}{\text{time}}\ ||\ O(1)\ \color{#7f5f3f}{\text{memory}}}}\)

int main()
{
    int n, k;
    cin >> n >> k;

    int mx = 0;
    ll res = 0;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        res += x;
        mx = max(mx, x);
    }

    cout << (res - mx) + max(0, mx - k) + 1;
    return 0;
}