meet in the middle + 二分判定
注意在双指针逼近时，相等的数带来的影响
#include#include #define N 262500using namespace std;int n,k,a[40],half,note;int tmp1[N],sum1,tmp2[N],sum2;int l,r,mid,ans;void dfs(int now,int tot,int *tmp,int &sum){ if(now>note) { tmp[++sum]=tot; return; } dfs(now+1,tot,tmp,sum); dfs(now+1,tot+a[now],tmp,sum);} bool check(){ int j=sum2,cnt1,cnt2,tot=0,last=0; for(int i=1;i<=sum1;i++) { while(j && tmp1[i]+tmp2[j]>mid) j--; if(!j) break; cnt1=cnt2=1; while(i 1 && tmp2[j-1]==tmp2[j]) j--,cnt2++; tot+=last; if(tot>=k) return false; last=cnt1*cnt2; } return true;}int main(){ scanf("%d%d",&n,&k); half=n>>1; for(int i=1;i<=n;i++) scanf("%d",&a[i]),r+=a[i]; note=half; dfs(1,0,tmp1,sum1); note=n; dfs(half+1,0,tmp2,sum2); sort(tmp1+1,tmp1+sum1+1); sort(tmp2+1,tmp2+sum2+1); while(l<=r) { mid=l+r>>1; if(check()) ans=mid,l=mid+1; else r=mid-1; } printf("%d",ans);}