Question

Пещера с монстрами Юный программист Коля играет в компьютерную игру. Чтобы пройти очередной уровень в этой игре, ему нужно зайти в пещеру с 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) — выносливость героя.Выходные данныеВыведите ответ на задачу.ПримерыВвод105 20 7 4 18 19 19 3 10 225Вывод5Решить на c++!!

Answer 1

Ответ:

#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;

}

}

Объяснение:

Answer 2

Конечно, вот C++ код для решения этой задачи:

cppCopy code
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n; // количество монстров
    cin >> n;
    vector<int> monsterHealth(n);

    for (int i = 0; i < n; i++) {
        cin >> monsterHealth[i];
    }

    int m; // выносливость героя
    cin >> m;

    // Сортируем здоровье монстров по возрастанию
    sort(monsterHealth.begin(), monsterHealth.end());

    // Бинарный поиск для определения минимальной силы удара
    int left = 1; // минимальная сила удара
    int right = monsterHealth[n - 1]; // максимальная сила удара
    int result = -1;

    while (left <= right) {
        int mid = (left + right) / 2;
        long long totalHits = 0;

        for (int i = 0; i < n; i++) {
            totalHits += max(0, (monsterHealth[i] - mid + mid - 1) / mid);
        }

        if (totalHits <= m) {
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    cout << result << endl;
    return 0;
}

Этот код сначала считывает входные данные, сортирует здоровье монстров по возрастанию, а затем использует бинарный поиск для нахождения минимальной силы удара.