Задача

Країна Ужляндія має вигідне географічне розташування – її територія знаходиться на перетині важливих торгівельних шляхів. Одним із таких є торгівельний шлях, яким сусідня братська держава доставляє свої унікальні обігрівачі до інших країн.

На кордоні Ужляндії та братської держави, де починається цей шлях, розташований спеціальний пропускний пункт, через який щодня проїжджає потяг із величезною кількістю обігрівачів. Зовсім недавно між урядами двох братських країн було погоджено нові правила транзиту обігрівачів через територію Ужляндії на найближчі $N$ днів. Згідно з новим договором має обратися певне число $m$ – максимальна кількість обігрівачів в одному потязі. Тоді з кожного потяга, що транспортує $A_i$ обігрівачів, буде відвантажено рівно $ A_i -m $ одиниць іноземної продукції (звичайно, якщо $A_i > m$ , інакше ж потяг рухатиметься без зупинок і нічого відвантажено не буде). Власне це й буде плата за проходження потяга територією Ужляндії, вона еквівалентна грошовим витратам на утримання залізничних колій. Сумарна кількість відвантажених в Ужляндії за $N$ днів обігрівачів повинна бути не менша $K$, інакше країна зазнає збитків.

Стала відома кількість обігрівачів у потязі в кожен із $N$ днів (ця інформація надається за умовами контракту). Знайдіть максимальне число $m$, при якому Ужляндія не зазнає економічних збитків.

Формат вхідних даних

В першому рядку записано два числа $N$, $K$ ($1 \leqslant N \leqslant 10^6$, $1 \leqslant K \leqslant 2 \cdot 10^9$). В наступному рядку задано $N$ чисел – кількість обігрівачів у потязі в кожен з $N$ днів, що не перевищує $10^9$.

Формат вихідних даних

В єдиному рядку виведіть одне число – відповідь на задачу, гарантується, що відповідь завжди існує.

Пояснення до прикладу

Всього територією Ужляндії пройде $4$ потяги з $11, 6, 1$ та $8$ обігрівачами відповідно. Щоби країна не знала збитків, потрібно відвантажити не менше $7$ обігрівачів. Очевидно, що максимальне можливе $m$, яке задовольнить цю умову, буде рівне $6$, тоді з потягів буде відвантажено відповідно $5, 0, 0, 2$ обігрівачів, що в сумі дорівнює $7$ і задовольняє умову.

Тести

№	Вхідні дані	Вихідні дані
1	4 7 1 8 6 11	6
2	10 20 1 8 6 11 16 14 21 10 13 4	11
3	5 10 12 4 3 6 9	5
4	6 11 5 8 6 9 4 7	4
5	2 1 2 2	1

Код

#include <iostream>
#include <algorithm>
using namespace std;

long N, K;
long* A;

long sum_depending_on_mid(int m) {
    long summ = 0;
    for (int i = 0; i <= N - 1 ; i++) {
        if(A[i] > m) summ += A[i] - m;
    }
    return summ;
}

int main() {
    cin >> N >> K;
    A = new long[N];
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    sort(A, A + N);
    long low = 0;
    long high = A[N - 1];
    long mid = 0;
    while (low != high and sum_depending_on_mid(mid = (low + high) / 2) != K) {
        long past_low = low;
        long past_high = high;
        if (sum_depending_on_mid(mid) < K) {
            high = mid;
        } else low = mid;
        if (past_low == low and past_high == high) {
            cout << mid;
            return 0;
        }
    }
    cout << mid;
    delete[] A;
}

#include <iostream>

#include <algorithm>

using namespace std;

long N, K;

long* A;

long sum_depending_on_mid(int m) {

long summ = 0;

for (int i = 0; i <= N - 1 ; i++) {

if(A[i] > m) summ += A[i] - m;

}

return summ;

}

int main() {

cin >> N >> K;

A = new long[N];

for (int i = 0; i < N; i++) {

cin >> A[i];

}

sort(A, A + N);

long low = 0;

long high = A[N - 1];

long mid = 0;

while (low != high and sum_depending_on_mid(mid = (low + high) / 2) != K) {

long past_low = low;

long past_high = high;

if (sum_depending_on_mid(mid) < K) {

high = mid;

} else low = mid;

if (past_low == low and past_high == high) {

cout << mid;

return 0;

}

cout << mid;

delete[] A;

}

Рішення

Для знаходження числа $m$ я використовував бінарний пошук, перед цим зробивши сортування по зростанню елементів в масиві. Отже, вся задача зводиться до використання бінарного пошуку, та функції яка рахує $\sum\limits_{i=0}^{n-1} A_i — m$, при $A_i > m$ ($m$ — значення mid; $n$ — кількість елементів в масиві; $A_i$ — значення $i$-го елемента масиву). Далі ця сума порівнюється з $K$ для подальшої роботи пошуку та знаходження числа $m$. Якщо такого числа $m$ не існує ми шукаємо найближче, при якому країна не зазнає збитків.