爆搜出奇迹 骗分过样例？
二分搜索+花式剪枝即可AC
太玄学了 不是很懂
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
// <1082.cpp> - Wed Mar 8 09:18:15 2017 // This file is created by XuYike's black technology automatically. // Copyright (C) 2015 ChangJun High School, Inc. // I don't know what this program is. #include <iostream> #include <vector> #include <algorithm> #include <cstring> #include <cstdio> #include <cmath> using namespace std; typedef long long lol; template<typename T> inline void gg(T &res){ res=0;T fh=1;char ch=getchar(); while((ch>'9'||ch<'0')&&ch!='-')ch=getchar(); if(ch=='-')fh=-1,ch=getchar(); while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar(); res*=fh; } inline int gi(){int x;gg(x);return x;} inline lol gl(){lol x;gg(x);return x;} const int MAXN=1010; const int INF=1e9; int n,m,a[MAXN],b[MAXN],sa,sb[MAXN]; bool dfs(int x,int t,int s,int w){ if(!t)return 1; if(w<0)return 0; for(int i=max(x,s);i<=n;i++){ if(a[i]<b[t])continue; a[i]-=b[t]; bool g; if(a[i]<b[1]){ swap(a[i],a[n--]); g=dfs(x,t-1,(b[t]==b[t-1])*i,w-a[n+1]); swap(a[i],a[++n]); }else g=dfs(x,t-1,(b[t]==b[t-1])*i,w); a[i]+=b[t]; if(g)return 1; } return 0; } int main(){ n=gi(); for(int i=1;i<=n;i++)sa+=(a[i]=gi()); m=gi(); for(int i=1;i<=m;i++)b[i]=gi(); sort(a+1,a+n+1); sort(b+1,b+m+1); for(int i=1;i<=m;i++)sb[i]=sb[i-1]+b[i]; int l=0,r=m; while(l<r){ int m=l+r+1>>1; if(dfs(1,m,0,sa-sb[m]))l=m; else r=m-1; } printf("%d",l); return 0; } |
说点什么