首页 > 代码库 > 独木舟问题
独木舟问题
以前一直一位set.end()是代表最后一个元素,原来只是个标记,怪不得一直出错,同时erase在multiset中会删除相同的元素。
本题很明显的greedy,排列后前后两个元素能否组合,不能删除最大元素,再组合,写的比较蠢,不想改了
#include<iostream> #include<set> using namespace std; int main() { int N; cin>>N; while(N--) { int w, n; cin>>w>>n; multiset<int,greater<int> >People; int Eachweight; for(int i=1;i<=n;i++) { cin>>Eachweight; People.insert(Eachweight); } int result=0; while(People.size()!=0) { multiset<int>::iterator it=People.begin(); int tempstart=*it; it=--People.end(); int tempend=*it; if((tempstart+tempend<=w)) { result++; People.erase(People.begin()); People.erase(--People.end()); } else { result++; People.erase(People.begin()); } if(People.size()==1) { result++; People.erase(People.begin()); } } cout<<result<<endl; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。