Greedy Algorithms
Being greedy for Water
You are given container full of water. Container can have limited amount of water. You also have N bottles to fill. You need to find the maximum numbers of bottles you can fill.
Input: First line contains one integer, T, number of test cases. First line of each test case contains two integer, N and X, number of bottles and capacity of the container. Second line of each test case contains N space separated integers, capacities of bottles.
Output: For each test case print the maximum number of bottles you can fill.
#include <bits/stdc++.h>
using namespace std;
int main() {
int T;
cin >> T;
while (T--) {
int numberOfBottles, capacityOfTheContainer;
cin >> numberOfBottles >> capacityOfTheContainer;
int A[numberOfBottles];
for (int i = 0; i < numberOfBottles; i++) {
cin >> A[i];
}
sort(A, A + numberOfBottles);
int capacity = 0, noOfBottlesFilled = 0;
for (int i = 0; i < numberOfBottles; i++) {
capacity = capacity + A[i];
if (capacity <= capacityOfTheContainer)
noOfBottlesFilled++;
else
break;
}
cout << noOfBottlesFilled << endl;
}
}
Last updated
Was this helpful?