思路
这道题我们要用贪心思想,每次优先压缩压缩率高的,就是指压缩后减少的空间更大的。
我们不断地压缩文件,直到空间够了,就直接退出输出答案。
这里要特判如果空间不压缩就够了就直接输出$0$,如果空间压缩后也不够就输出$-1$。
代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
int n,m;
int a[N],b[N],c[N];
int main () {
cin >> n >> m;
LL sum1 = 0,sum2 = 0;
for (int i = 1;i <= n;i++) {
cin >> a[i] >> b[i];
c[i] = a[i] - b[i];
sum1 += a[i],sum2 += b[i];
}
if (sum2 > m) {
puts ("-1");
return 0;
}
sort (c + 1,c + 1 + n,[](int x,int y) {
return x > y;
});
int ans = 0;
for (int i = 1;i <= n;i++) {
if (sum1 <= m) break;
sum1 -= c[i];
ans++;
}
cout << ans << endl;
return 0;
}