Сложность: medium
Дан массив целых чисел nums и целое число threshold. Мы выберем положительный целый делитель, разделим все элементы массива на него и суммируем результат деления. Найдите наименьший делитель, такой что результат, упомянутый выше, меньше или равен threshold.
Каждый результат деления округляется до ближайшего большего целого числа. (Например: 7/3 = 3 и 10/2 = 5).
Гарантируется, что решение существует.
Пример:
Input: nums = [1,2,5,9], threshold = 6
Output: 5
Explanation: We can get a sum to 17 (1+2+5+9) if the divisor is 1.
If the divisor is 4 we can get a sum of 7 (1+1+2+3) and if the divisor is 5 the sum will be 5 (1+1+1+2).
👨💻 Алгоритм:
1⃣Найдите максимальный элемент массива nums и сохраните его в переменной maxElement.
2⃣Итерация по всем делителям от 1 до maxElement:
Инициализируйте две переменные: sumOfDivisionResults для хранения суммы результатов деления и thresholdExceeded для указания, превышен ли порог.
Итерация по всем элементам массива nums: добавьте результат деления, округленного до ближайшего большего целого числа, в переменную sumOfDivisionResults. Если сумма превышает threshold, установите thresholdExceeded в true и прекратите итерацию по массиву nums.
3⃣Проверьте, был ли превышен порог:
Если порог не был превышен, текущий делитель является наименьшим делителем, поэтому верните его.
Если не найдено возможного делителя, верните -1.
😎 Решение:
class Solution {
public:
int smallestDivisor(vector<int>& nums, int threshold) {
int maxElement = *max_element(nums.begin(), nums.end());
for (int divisor = 1; divisor <= maxElement; ++divisor) {
int sumOfDivisionResults = 0;
bool thresholdExceeded = true;
for (int num : nums) {
sumOfDivisionResults += (num + divisor - 1) / divisor;
if (sumOfDivisionResults > threshold) {
thresholdExceeded = false;
break;
}
}
if (thresholdExceeded) {
return divisor;
}
}
return -1;
}
};Ставь 👍 и забирай 📚 Базу знаний