Задача на с++ по бинарному поиску
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 шт):
Поставил 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;
}