1498B - Box Fitting (优先队列) ゝ一纸荒年。 2021-07-16 11:45 268阅读 0赞 [题目][Link 1] 思路:开一个优先队列存放每一行(高度1)还剩余的长度,将所有的木块从大到小排序,1开始遍历,如果优先队列中还能容纳最大的长度比当前木块大则加入到当前高度所在行,否则另开一行存放。 Code: #include<iostream> #include<algorithm> #include<set> #define ll long long using namespace std; const int Max = 1e6 + 5; int lst[Max]; int main() { int t;cin >> t; while (t--) { int n, w;cin >> n >> w; for (int i = 1;i <= n;i++)cin >> lst[i]; sort(lst + 1, lst + 1 + n, greater<int>()); multiset<int,greater<int>> set; set.insert(w); for (int i = 1;i <= n;i++) { int a = *set.begin(); if (a >= lst[i]) { set.insert(a - lst[i]); set.erase(set.find(a)); } else set.insert(w - lst[i]); } cout << set.size() << endl; } } [Link 1]: https://codeforc.es/problemset/problem/1498/B
还没有评论,来说两句吧...