首页 > 代码库 > 独木舟问题

独木舟问题

以前一直一位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;

	}

}