栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

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

C/C++/C# 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

[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
求救!

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/528825.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号