聯賽模拟測試24 B. 答題 折半枚舉

題目描述

分析

暴力的思想是把 \(2^n\) 種得分枚舉出來，每一種得分的機率都是相同的，然後從小到大累加，直到大于等于所給的機率

把問題轉化一下，就變成了在 \(2^n\) 種元素中求 \(k\) 小值

\(n\) 的範圍是 \(40\)， \(2^{40}\) 不可過，但是 \(2^{20}\)可過

把序列分成兩半，每一半的大小都是 \(2^{n/2}\),分别排序

二分 \(k\) 大值，在另一半中查找與目前這一半中某個元素的和恰好小于等于目前值的元素個數

因為元素大小具有單調性，是以二分沒有必要，改成雙指針

時間複雜度 \(log(n \times m) \times 2^{n/2}\)

代碼

#include<cstdio>
#include<algorithm>
#include<cmath>
#define rg register
typedef long long ll;
const int maxn=22;
int n,a[maxn<<1],bef[1<<maxn],lat[1<<maxn],tp1,tp2,zg;
ll k;
double p,now;
void dfs1(int now,int tot){
	if(now>n/2){
		bef[++tp1]=tot;
		return;
	}
	dfs1(now+1,a[now]+tot);
	dfs1(now+1,tot);
}
void dfs2(int now,int tot){
	if(now>n){
		lat[++tp2]=tot;
		return;
	}
	dfs2(now+1,a[now]+tot);
	dfs2(now+1,tot);
}
bool jud(int val){
	rg int now=tp2;
	rg ll ans=0;
	for(rg int i=1;i<=tp1;i++){
		while(lat[now]+bef[i]>val && now>0) now--;
		ans+=now;
	}
	return ans>=k;
}
int main(){
	scanf("%d%lf",&n,&p);
	for(rg int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		zg+=a[i];
	}
	now=1.0;
	for(rg int i=1;i<=n;i++){
		now=now*0.5;
	}
	k=(ll)std::ceil((double)p/now);
	dfs1(1,0);
	dfs2(n/2+1,0);
	std::sort(bef+1,bef+1+tp1);
	std::sort(lat+1,lat+1+tp2);
	rg int l=0,r=zg,mids;
	while(l<=r){
		mids=(l+r)>>1;
		if(jud(mids)) r=mids-1;
		else l=mids+1;
	}
	printf("%d\n",l);
	return 0;
}