暴力枚举,选对数据结构,不怕超时
查看原帖
暴力枚举,选对数据结构,不怕超时
1346964
XianZai楼主2024/6/18 08:44

第一次枚举使用了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;
}

2024/6/18 08:44
加载中...