折半搜索【2024华为智联杯 K.时光】

假如一个序列n个物品，每个都可以选择选择或不选，一共2^n个方案，可能会超时，但考虑将整个搜索过程折半，分为前n/2个，后n/2个去进行搜索，最后将两个答案序列进行合并，复杂度会缩小很多

例题

初看可能想到背包之类的，但数据范围达到了1e9级别，考虑选择的集合确定的情况下，价值一定是从大到小进行选择，先整体按价值进行排序，分为前一半后一半，将各自方案存入数组。注意考虑到计算，后一半需要以选择的个数存入不同数组

在确定前一半中选择的方案后，以剩余时间二分查找后一半可选择的一段前缀，预处理出这一段前缀的最大值，再通过个数乘上前一半的选择的和，以此更新答案

"华为智联杯"无线程序设计大赛暨2024年上海市大学生程序设计竞赛 K.时光

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=35,M=8e4+86;
struct node{int x,y;
}a[N];
int n,m,p[30][M];
bool cmp(node a,node b)
{return a.y>b.y;
}
struct abc{int sm,u,v,vv;
}b[M],c[30][M];
void dfs(int st,int ed,int sm,int u,int v,int vv)
{if(st>ed){ b[++b[0].sm]={sm,u,v-vv,vv};return ;}dfs(st+1,ed,sm+1,u+a[st].x,v+vv+a[st].y,vv+a[st].y );dfs(st+1,ed,sm,u,v,vv);
}
void dfs2(int st,int ed,int sm,int u,int v,int vv)
{if(st>ed){c[sm][++c[sm][0].sm]={sm,u,v-vv,vv};return ;}dfs2(st+1,ed,sm+1,u+a[st].x,v+vv+a[st].y,vv+a[st].y );dfs2(st+1,ed,sm,u,v,vv);
}
bool cmpp(abc a,abc b)
{if(a.u==b.u ) return a.v>b.v;return a.u<b.u;
} 
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i].x;for(int i=1;i<=n;i++) cin>>a[i].y;sort(a+1,a+1+n,cmp);dfs(1,n/2,0,0,0,0);dfs2(n/2+1,n,0,0,0,0);for(int i=1;i<=n-(n/2);i++){sort(c[i]+1,c[i]+c[i][0].sm+1,cmpp);p[i][0]=0;for(int j=1;j<=c[i][0].sm;j++) p[i][j]=max(p[i][j-1],c[i][j].v);}int as=0;for(int i=0;i<=b[0].sm;i++){if(b[i].u>m) continue;int ass=b[i].v;as=max(as,b[i].v);int t=m-b[i].u;if(t<=0) continue;for(int j=1;j<=n-(n/2);j++){int l=1,r=c[j][0].sm;while(l<r){int mid=(l+r+1)/2;if(c[j][mid].u<=t) l=mid;else r=mid-1;}if(c[j][l].u>t) l--;if(i==0) as=max(as,p[j][l]); else if(l) as=max(as,ass+b[i].vv*j+p[j][l]);}}cout<<as<<endl;return 0;}