CF1498-B.Box Fitting
2021/5/23 10:28:34
本文主要是介绍CF1498-B.Box Fitting,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
CF1498-B.Box Fitting
题意
给出 n n n个长条,每个长条保证可以表示为 2 x 2^x 2x的形式,问你如果一个宽度为 w w w的盒子最少要多高才能装下这些长条。
思路
贪心。将长条按照长度从大到小排序,对于每一层我们尽量将它装满再装下一层。
可以用 m u l t i s e t multiset multiset维护每一层剩余的空间。对于当前要放入盒子的长条,在集合中 l o w e r _ b o u n d lower\_bound lower_bound得到一个合适的位置,如果没有那就新开一层,答案加一;如果有就将该层的空间减少,还有剩余就再次加入到集合中。
代码
#include <algorithm> #include <iostream> #include <cstring> #include <stack> #include <cstdlib> #include <map> #include <queue> #include <cctype> #include <cmath> #include <cstdio> #include <set> #include <ctime> #define rep(i, s, t) for (int i = (s); i < (t); i++) #define wa std::cerr << "----WARN----" << std::endl; #define wl std::cerr << "********" << std::endl; #define wr std::cerr << "~~~~~~~~" << std::endl; #define PII pair<int, int> #define mp(a, b) make_pair(a, b) #define fr first #define sc second typedef long long LL; const int MOD = 1000000007; const int INF = 0x3f3f3f3f; const LL LINF = 1LL * 0x3f3f3f3f3f3f3f3f; inline int read(); const int N = 100005; int a[N]; void solve() { int n, w; std::cin >> n >> w; rep (i, 0, n) { std::cin >> a[i]; } std::sort(a, a + n, std::greater<int>()); std::multiset<int> s; int ans = 0; rep (i, 0, n) { if (s.empty()) { if (a[i] != w) s.insert(w - a[i]); ans++; } else { auto it = s.lower_bound(a[i]); if (it == s.end()) { if (w != a[i]) s.insert(w - a[i]); ans++; continue; } else { int t = *it; s.erase(it); if (t != a[i]) s.insert(t - a[i]); } } } std::cout << ans << std::endl; } inline int read() { int s = 0, w = 1; char ch = getchar(); while (!isdigit(ch)) { if (ch == '-') w = -1; ch = getchar(); } while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); } return s * w; } signed main() { // freopen("in.txt", "r", stdin); int T = 1; T = read(); while (T--) solve(); return 0; }
这篇关于CF1498-B.Box Fitting的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-07fastcgi 是什么-icode9专业技术文章分享
- 2024-10-07fastcgi 的详细使用教程介绍-icode9专业技术文章分享
- 2024-10-07git如何更新单个文件到本地-icode9专业技术文章分享
- 2024-10-07如何使用ASM(Abstract Syntax Tree Manipulation)技术来修改第三方AAR依赖中的函数-icode9专业技术文章分享
- 2024-10-07Activity 跳转时间耗时很长怎么优化解决-icode9专业技术文章分享
- 2024-10-07Androud Toast 有哪些常用的第三方组件-icode9专业技术文章分享
- 2024-10-07在viewmodel中怎么使用 mmkv?-icode9专业技术文章分享
- 2024-10-07MMKV.defaultMMKV() 是单例模式吗?-icode9专业技术文章分享
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享