Задача на с++ по бинарному поиску

C. Веревочки

ограничение по времени на тест: 1 секунда

ограничение по памяти на тест: 256 мегабайт

ввод: стандартный ввод

вывод: стандартный вывод

С утра шел дождь, и ничего не предвещало беды. Но к обеду выглянуло солнце, и в лагерь заглянула СЭС. Пройдя по всем домикам и корпусам, СЭС вынесла следующий вердикт: бельевые веревки в жилых домиках не удовлетворяют нормам СЭС. Как выяснилось, в каждом домике должно быть ровно по одной бельевой веревке, и все веревки должны иметь одинаковую длину. В лагере имеется n бельевых веревок и k домиков. Чтобы лагерь не закрыли, требуется так нарезать данные веревки, чтобы среди получившихся веревочек было k одинаковой длины. Размер штрафа обратно пропорционален длине бельевых веревок, которые будут развешены в домиках. Поэтому начальство лагеря стремиться максимизировать длину этих веревочек.

Входные данные

В первой строке заданы два числа – n и k (1 ≤ n, k ≤ 10001). Далее в каждой из последующих n строк записано по одному числу ai (1 ≤ ai ≤ 108) – длине i-й бельевой веревки. Длина веревки задана в сантиметрах. Все длины лежат в интервале от 1 сантиметра до 100 километров включительно.

Выходные данные

В выходной файл следует вывести одно целое число — максимальную длину веревочек, удовлетворяющую условию, в сантиметрах. В случае, если лагерь закроют, выведите 0.

Пример:

входные данные

4 11
802
743
457
539

выходные данные

200
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int l = 0;
    int r = *max_element(a.begin(), a.end());
    while (r > l + 1) {
        int m = (l + r) / 2;
        int sum = 0;
        for (int x : a){
            sum += x / m;
        }
        if (sum < k) {
            r = m;
        } else {
            l = m;
        }
    }
    cout << l << endl;
    return 0;
}

написал вот такой код, но выдает ошибку на 5 тесте. Помогите, пожалуйста.


Ответы (1 шт):

Автор решения: Arzi

Поставил long long, поменял границу бинарного поиска, и заработало:

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long int
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    int l = 0;
    int r = 1e9;
    while (l != r - 1) {
        int m = (l + r) / 2;
        ll sum = 0;
        for (int x : a){
            sum += x / m;
        }
        if (sum < k) {
            r = m;
        } else {
            l = m;
        }
    }
    cout << l << endl;
    return 0;
}
→ Ссылка