【正经题解】歌曲压缩

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

// 音乐结构体
struct Music {
    int originalSize;  // 初始大小
    int compressedSize;  // 压缩后大小
};

// 用于 priority_queue 的比较函数
struct Compare {
    bool operator()(const Music& m1, const Music& m2) const {
        return (m1.originalSize - m1.compressedSize) < (m2.originalSize - m2.compressedSize);
    }
};

int main() {
    priority_queue<Music, vector<Music>, Compare> pq;  // 使用自定义比较函数的优先队列
    int numSongs, flashDriveCapacity;
    cin >> numSongs >> flashDriveCapacity;
    
    int totalSize = 0;  // 所有歌曲的总大小
    int minCompressedSongs = 0;  // 最少需要压缩的歌曲数

    vector<Music> songs(numSongs);

    // 输入音乐信息
    for (int i = 0; i < numSongs; i++) {
        cin >> songs[i].originalSize >> songs[i].compressedSize;
        pq.push(songs[i]);
        totalSize += songs[i].originalSize;
    }

    // 按照压缩效益排序，优先压缩效益高的歌曲
    while (totalSize > flashDriveCapacity && !pq.empty()) {
        totalSize -= (pq.top().originalSize - pq.top().compressedSize);
        pq.pop();
        minCompressedSongs++;
    }

    // 判断是否能够使所有歌曲适合闪存驱动器
    if (totalSize <= flashDriveCapacity) {
        cout << minCompressedSongs;
    } else {
        cout << "-1";
    }

    return 0;
}