练83.1 压缩歌曲

解题思路

要装下全部歌曲，总原体积S超m时需节省S-m。每首可节省ai-bi，按节省量降序逐首压缩，第一次降到容量以内的首数最少；全部压缩仍超则-1。

正确性说明

依照上述推导，逐步维护已处理部分的有效状态。每一步都完成当前项的贡献且不改变已确定的次序，结束时输出的状态恰好对应题目要求。

易错点

压缩的是全部歌曲中的部分，不是丢掉歌曲。

复杂度

时间O(n log n)，空间O(n)。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long m;
    cin >> n >> m;
    vector<long long> save(n);
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        long long a, b;
        cin >> a >> b;
        sum += a;
        save[i] = a - b;
    }
    sort(save.begin(), save.end(), greater<long long>());
    int count = 0;
    while (sum > m && count < n) {
        sum -= save[count++];
    }
    cout << (sum <= m ? count : -1) << "\n";
    return 0;
}