[C++贪心习题]压缩歌曲

[C++贪心习题]压缩歌曲,第1张

[C++贪心习题]压缩歌曲

(新人求教!判题正确率92%,有一个答案错误×,求指点!)

题目大致如下:
给定歌曲数量,储存大小与每首歌压缩前后的大小,问最少压缩几首歌才能全部装入,若不能则输出-1.
样例输入:
4 21
10 8
7 4
3 1
5 4
样例输出:
2

解本题时不要被题目吓到,本人一开始看题想到动态规划,定睛一看发现只有能放与不能放两种情况,于是长舒一气。

思路如下:
先判断特殊情况,也就是能否装下,否则输出-1并结束程序
之后统计所有歌曲压缩前的大小总和,并将歌曲以压缩能够节省的空间大小降序排序,已用尽可能少的压缩换取尽可能多的空间
之后循环,一个一个压缩,直到空间可以被容纳

代码如下:

#include 
using namespace std;
struct A{
    int y;
    int x;
} k[100005];
bool cmp(const A &p, const A &q){
    return p.y - p.x > q.y - q.x;
}
int main(){
    int n,m, s2 = 0, s1 = 0, ans = 0;
    cin >> n >> m;
    for (int i = 0; i < n; i++){
        cin >> k[i].y >> k[i].x;
        s2 += k[i].x;
        s1 += k[i].y;
    }
    if (s2 > m) {
        cout << -1;
        return 0;
    }
    if (s2 == m){
        cout << 0;
        return 0;
    }
    sort (k, k + n, cmp);
    for (int i = 0; i < n && s1 > m; i++){
        s1 -= k[i].y - k[i].x;
        ans++;
    }
    if (s1 <= m)
        cout << ans;
    else
        cout << -1;
    return 0;
}

92%?错在哪里了啊 QAQ
求救!

欢迎分享,转载请注明来源:内存溢出

原文地址:https://54852.com/zaji/5520634.html

(0)
打赏 微信扫一扫微信扫一扫 支付宝扫一扫支付宝扫一扫
上一篇 2022-12-13
下一篇2022-12-13

发表评论

登录后才能评论

评论列表(0条)

    保存