Jamal is trying to install a new app on his smart phone, but he is getting an error message:
“Memory is full”.
He loves his already installed apps, so he wants to remove the minimum number of them to be
able to install the new app.
Assume that his phone memory is k MBs, the new app size is m MBs and that there are n
installed apps. You are given a list of n positive integers representing the sizes of the installed
apps.
Find the minimum number of apps that should be removed.
Input
The first line of input contains one integer T, the number of test cases(1≤T≤128).
Each test case begins with three integers:k,m,n(1≤m≤k≤32,768)and(1≤n≤100).The next
line contains n space-separated integers representing the sizes of the installed apps.
Output
For each test case, print the minimum number of apps Jamal has to remove to be able to install.
thenewapp.
input
2
7 7 5
1 2 1 1 1
14 13 5
1 2 2 1 2
output
5
4
題意：
一個人的手機(jī)內(nèi)存不足戈稿，已知他的手機(jī)內(nèi)存和手機(jī)里每個app所占的內(nèi)存凤优，問：如果要再下載一個app，最少要卸載幾個app沸柔。這道題主要就是貪心他挎，一直卸載當(dāng)前占內(nèi)存最大的app琼牧，直到空閑內(nèi)存大于等于所需要下載的app的內(nèi)存毅弧，統(tǒng)計一下卸載了幾個app就好了欢际。注意排序時不要越界。
代碼：
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
int main()
{
int a[105];
int k, m, n, i, t, j, s;
scanf("%d", &t);
for (j = 0;j < t;j ++)
{
scanf("%d%d%d", &k, &m, &n);
s = k;
for (i = 0;i < n;i ++)
{
scanf("%d", &a[i]);
s -= a[i];
}
sort(a, a+n);
for (i = n-1;i >= 0;i --)
{
s += a[i];
if (s >= m)
break;
}
printf("%d\n", n-i);
memset(a, 0, sizeof(a));
}
return 0;
}
