![[C++贪心习题]压缩歌曲,第1张 [C++贪心习题]压缩歌曲,第1张](/aiimages/%5BC%2B%2B%E8%B4%AA%E5%BF%83%E4%B9%A0%E9%A2%98%5D%E5%8E%8B%E7%BC%A9%E6%AD%8C%E6%9B%B2.png)
(新人求教!判题正确率92%,有一个答案错误×,求指点!)
题目大致如下:
给定歌曲数量,储存大小与每首歌压缩前后的大小,问最少压缩几首歌才能全部装入,若不能则输出-1.
样例输入:
4 21
10 8
7 4
3 1
5 4
样例输出:
2
解本题时不要被题目吓到,本人一开始看题想到动态规划,定睛一看发现只有能放与不能放两种情况,于是长舒一气。
思路如下:
先判断特殊情况,也就是能否装下,否则输出-1并结束程序
之后统计所有歌曲压缩前的大小总和,并将歌曲以压缩能够节省的空间大小降序排序,已用尽可能少的压缩换取尽可能多的空间
之后循环,一个一个压缩,直到空间可以被容纳
代码如下:
#includeusing 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
求救!
欢迎分享,转载请注明来源:内存溢出
微信扫一扫
支付宝扫一扫
评论列表(0条)