[luogu2329 SCOI2005] 栅栏(二分+搜索)

Solution

纯搜索80分，加二分90分，再补一个小剪枝满分qwq

真.小剪枝：如果下一个的需求和当前相同，那么不需要再次从头开始试(看代码就明白了233)

Code

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define F(i,a,b) for(register int i=(a);i<=(b);i++)

using namespace std;

inline int read() {

	int x=0,f=1;char c=getchar();

	while(!isdigit(c)) {if(c=='-')f=-f;c=getchar();}

	while(isdigit(c)) x=(x<<1)+(x<<3)+c-48,c=getchar();

	return x*f;

}

const int M=55,N=1010;

int m,n,ans,tot;

int da[M],li[M],nd[N],s[N];

bool dfs(int las,int lef) {

	if(!las) return 1;

	F(i,lef,m) if(nd[las]<=da[i]) {

		da[i]-=nd[las];

		bool fla=dfs(las-1,nd[las]==nd[las-1]?i:1);

		da[i]+=nd[las];

		if(fla) return 1;

	}

	return 0;

}

int main() {

	m=read();F(i,1,m) da[i]=read(),tot+=da[i];

	n=read();F(i,1,n) nd[i]=read();

	sort(da+1,da+1+m);sort(nd+1,nd+1+n);

	F(i,1,n) s[i]=s[i-1]+nd[i];

	while(s[n]>tot) n--;

	int l=1,r=n;

	while(l<=r) {

		int mid=(l+r)>>1;

		if(dfs(mid,1)) ans=mid,l=mid+1;

		else r=mid-1;

	}

	printf("%d",ans);

	return 0;

}

巴特西

[luogu2329 SCOI2005] 栅栏(二分+搜索)

Solution

Code

最新文章

热门文章