Problem: Mark and Toys

Mark and Jane are very happy after having their first kid. Their son is very fond of toys. Therefore, Mark wants to buy some toys for his son. But he has a limited amount of money. But he wants to buy as many toys as he can. So, he is in a dilemma and is wondering how he can maximize the number of toys he can buy. He has N items in front of him, tagged with their prices and he has only K rupees.

Now, you being Mark’s best friend have the task to help him buy as many toys for his son as possible.

Input Format
The first line will contain two inputs N and K, followed by a line containing N integers separated by a single space indicating the products’ prices.

Output Format
Maximum number of toys Mark can buy for his son.

Constraints
1<=N<=105
1<=K<=109
1<=price of any toy<=109

Sample Input

7 50
1 12 5 111 200 1000 10

Sample Output

4

Explanation

He can buy only 4 toys at most. These toys have the following prices: 1,12,5,10.

 

#include <stdio.h>

//First, you need to sort the array, so QuickSort is the best algorithm for this
void QuickSort(unsigned long *a,long l,long r);

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
long N,K,i,Count=0;
scanf(“%ld%ld”,&N,&K);
unsigned long a[N];
for(i=0;i<N;++i)
scanf(“%ld”,&a[i]);
QuickSort(a,0,N-1);
//After sorting, we take K subtract a[i] (with i run from zero to N-1), each step we raise Count’s value by 1
//If(K<a[i]) , it means we can not buy toys anymore, so “break”, and print the result to STDOUT
for(i=0;i<N;++i){
if(K<a[i])
break;
K-=a[i];
Count++;
}
printf(“%ld”,Count);
return 0;
}

void QuickSort(unsigned long *a,long l,long r){
unsigned long x,temp;
long i,j;
x=a[(l+r)/2];
i=l; j=r;
do{
while(a[i]<x) ++i;
while(a[j]>x) –j;
if(i<=j){
temp=a[i];
a[i]=a[j];
a[j]=temp;
i++; j–;
}
}while(i<j);
if(l<j)
QuickSort(a,l,j);
if(i<r)
QuickSort(a,i,r);
}

Advertisements