(新人求教!判题正确率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
求救!


![[C++贪心习题]压缩歌曲 [C++贪心习题]压缩歌曲](http://www.mshxw.com/aiimages/31/528825.png)
