Сложность: easy
У вас есть несколько яблок и корзина, которая может выдержать до 5000 единиц веса.
Дан целочисленный массив weight, где weight[i] — это вес i-го яблока. Верните максимальное количество яблок, которые можно положить в корзину.
Пример:
Input: weight = [100,200,150,1000]
Output: 4
Explanation: All 4 apples can be carried by the basket since their sum of weights is 1450.
👨💻 Алгоритм:
1⃣Преобразование массива в мин-кучу:
Преобразуйте массив weight в мин-кучу, чтобы получить минимальные элементы первым.
2⃣Инициализация переменных:
Инициализируйте переменные apples для подсчета количества яблок и units для записи текущего веса корзины.
3⃣ Добавление яблок в корзину:
Пока текущий вес корзины меньше 5000 единиц и в куче остаются элементы:
Увеличивайте apples на 1.
Увеличивайте units на значение, извлеченное из кучи.
😎 Решение:
public class Solution {
public int MaxNumberOfApples(int[] weight) {
var heap = new SortedSet<int>(weight);
int apples = 0, units = 0;
foreach (var w in heap) {
if (units + w <= 5000) {
units += w;
apples++;
} else {
break;
}
}
return apples;
}
}Ставь 👍 и забирай 📚 Базу знаний