Пещера с монстрами
Юный программист Коля играет в компьютерную игру. Чтобы пройти очередной уровень в этой игре, ему нужно зайти в пещеру с n монстрами и убить их одного за другим. Монстры имеют здоровье h1,…,hn. Если герой Коли имеет силу X, то каждый удар героя по монстру будет уменьшать здоровье монстра на X. Монстр погибает, когда его здоровье становится меньше или равно нулю. Герой Коли имеет ограниченную выносливость, поэтому он сможет нанести не более чем m ударов. Таким образом, чтобы пройти уровень, необходимо победить всех монстров не более чем за m ударов.
В данный момент герой Коли имеет силу удара равную 0. Игрок может повысить силу удара своего героя до натурального числа X, но для этого ему придётся потратить X игровых очков. Коля не хочет тратить лишних очков, поэтому решил найти такое минимальное натуральное число X, которого будет достаточно для успешного прохождения пещеры с монстрами. Помогите Коле найти это число или выведите −1, если такого X не существует.
Входные данные
В первой строке входных данных задано натуральное число n (1≤n≤105) — количество монстров. Во второй строке заданы через пробел n целых чисел — здоровье монстров 1≤hi≤109. В третьей строке задано натуральное число m (1≤m≤109) — выносливость героя.
Выходные данные
Выведите ответ на задачу.
Примеры
Ввод
10
5 20 7 4 18 19 19 3 10 2
25
Вывод
5
Решить на c++!!
Юный программист Коля играет в компьютерную игру. Чтобы пройти очередной уровень в этой игре, ему нужно зайти в пещеру с n монстрами и убить их одного за другим. Монстры имеют здоровье h1,…,hn. Если герой Коли имеет силу X, то каждый удар героя по монстру будет уменьшать здоровье монстра на X. Монстр погибает, когда его здоровье становится меньше или равно нулю. Герой Коли имеет ограниченную выносливость, поэтому он сможет нанести не более чем m ударов. Таким образом, чтобы пройти уровень, необходимо победить всех монстров не более чем за m ударов.
В данный момент герой Коли имеет силу удара равную 0. Игрок может повысить силу удара своего героя до натурального числа X, но для этого ему придётся потратить X игровых очков. Коля не хочет тратить лишних очков, поэтому решил найти такое минимальное натуральное число X, которого будет достаточно для успешного прохождения пещеры с монстрами. Помогите Коле найти это число или выведите −1, если такого X не существует.
Входные данные
В первой строке входных данных задано натуральное число n (1≤n≤105) — количество монстров. Во второй строке заданы через пробел n целых чисел — здоровье монстров 1≤hi≤109. В третьей строке задано натуральное число m (1≤m≤109) — выносливость героя.
Выходные данные
Выведите ответ на задачу.
Примеры
Ввод
10
5 20 7 4 18 19 19 3 10 2
25
Вывод
5
Решить на c++!!
More Questions From This User See All
Answers & Comments
Ответ:
#include <iostream>
#include <vector>
#include <cctype>
#include <algorithm>
#include <iterator>
using namespace std;
#define ll long long
bool OK(vector<ll>h, int L, int n, int m) {
ll res = 0;
for (int i = 0; i < n; i++) {
res += (h[i] + L - 1) / L;
}
return (res <= m) ? true : false;
}
int main() {
int n;
cin >> n;
vector<ll> h(n);
vector<ll> ::iterator it;
for (int i = 0; i < h.size(); ++i) {
cin >> h[i];
}
int m;
cin >> m;
if (m < n) {
cout << -1;
}
else {
ll l = 0;
it = max_element(h.begin(), h.end());
ll r = *it;
while (r-l>1) {
int L = (r + l) / 2;
(OK(h, L, n, m)) ? r = L: l = L;
}
cout << r;
}
}
Объяснение: