第一次枚举使用了list容器,导致超时又超内存。这是因为list中可以包含重复元素,例如1+3=4的体积和2+2=4的体积是相等的。所以选set集合,轻松就过来。
#include<iostream>
#include<set>
using namespace std;
typedef set<int> MySet;
int main()
{
int V,n; cin>>V>>n;
MySet Set;
int remain=V;
for(int i=0;i<n;i++)
{
int v;cin>>v;
MySet SetTemp;//加入新物体导致的总体积
for(auto it=Set.begin();it!=Set.end();it++)
{
int VSum=*it+v;
if(VSum<=V)
SetTemp.insert(VSum);
}
for(auto it=SetTemp.begin();it!=SetTemp.end();it++)
{
//新物体加入后导致的总体积存入Set中
if(Set.insert(*it).second && V-*it<remain)remain=V-*it;
}
//新物体的单独体积存入Set中
if(v<=V)
{
Set.insert(v);
if(V-v<remain)remain=V-v;
}
}
cout<<remain;
}