题解：P10484 送礼物

· · 题解

思路

折半搜索。

看数据范围，2^{46} 肯定炸，但 2 \times 2^{23} 炸不了。

整个数组从中间劈成两半，对于每一半，求出礼物能组成的所有重量数，存在两个数组中。

把其中一个数组排序，遍历另一个数组，二分查找在另一个数组中满足条件的最大值。最后求出所有答案的最大值。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define re register
#define ri register int
#define rll register long long
#define ld long double
#define endl '\n'
#define fi first
#define se second
#define pii pair<int,int>
#define p_q priority_queue
#define iter iterator
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define nep(i,a,b) for(int i=(a);i>=(b);i--)
#define popcount __builtin_popcount
#define pb push_back
#define mem(a,x) memset((a),x,sizeof(a))
#define eps 1e-8
#define oper operator
#define mk make_pair
vector<ll>a,b;
ll n,g[55],w;
void dfs1(int l,int r,ll sum){
    if(l>r){
        if(sum<=w)a.pb(sum);//能搬动
        return ;
    }
    dfs1(l+1,r,sum+g[l]);
    dfs1(l+1,r,sum);
}
void dfs2(int l,int r,ll sum){
    if(l>r){
        if(sum<=w)b.pb(sum);//能搬动
        return ;
    }
    dfs2(l+1,r,sum+g[l]);
    dfs2(l+1,r,sum);
}
int main(){
    cin>>w>>n;
    for(int i=1;i<=n;i++) cin>>g[i];
    dfs1(1,(1+n)/2,0);//前一半
    dfs2((1+n)/2+1,n,0);//后一半
    ll maxx=0;
    sort(b.begin(),b.end());//排序
    for(int i=0;i<a.size();i++){
        ll sum=a[i];
        int l=0,r=b.size()-1,ans=0;
        while(l<=r){//二分查找满足条件的最大值
            int mid=(l+r)/2;
            if(b[mid]+a[i]<=w){
                l=mid+1;
                ans=mid;
            }else r=mid-1;
        }
        sum+=b[ans];
        maxx=max(maxx,sum);
    }
    cout<<maxx;//输出
    return 0;
}