首页 > 代码库 > SPOJ - VISIBLEBOX [multiset的使用]
SPOJ - VISIBLEBOX [multiset的使用]
tags:[STL][sort][贪心]
题解:
做法:先对数组a进行排序,再将数组a从头到尾扫一遍,使用multiset维护最小值,
如果,即将放入集合的数字>=最小值的两倍,那我们就删除掉多重集合的最小值。
最后,多重集合中元素的个数即为答案。
证明:“人生得意须尽欢,莫使金樽空对月”。当即将进入集合的箱子,装得下
最小的箱子时,若装入并非最小的箱子,或啥也不装,找不到更优解,喵!
#include <iostream> #include <cstdio> #include <set> #include <algorithm> using namespace std; multiset<int> s; int T, n, a[100000 + 10]; int main() { cin >> T; for(int t=1;t<=T;t++) { s.clear(); scanf("%d", &n); for(int i=1;i<=n;i++) { scanf("%d", &a[i]); } sort(a+1, a+1+n); s.insert(a[1]); for(int i=2;i<=n;i++) { int minc = *s.begin(); if(a[i] >= 2*minc) { s.erase(s.begin()); } s.insert(a[i]); } printf("Case %d: %d\n", t, (int)s.size()); } }
SPOJ - VISIBLEBOX [multiset的使用]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。