@[菜♂虚♂鲲](/user/216349) 我刚刚研究了一道YJH秒过的蓝题
by HeartBlock_Love @ 2019-11-11 23:11:48
```
#include<cstdio>
#include<algorithm>
#include<cctype>
using namespace std;
template <class code>inline code read(const code &a)
{
code x=0;short w=0;char ch=0;
while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
while(isdigit(ch)) {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return w?-x:x;
}
int a[55],b[1100],n,m,qz[1100],now[100],sum=0,waste=0,mid;
inline bool check(int rr,int ww){
if(!rr)return 1;
if(sum-waste<qz[mid])return 0;
for(int i=ww;i<=n;++i)
if(now[i]>=b[rr]){
now[i]-=b[rr];
if(now[i]<b[1])waste+=now[i];
if(b[rr]==b[rr-1]){
if(check(rr-1,i))return 1;
}
else if(check(rr-1,1))return 1;
if(now[i]<b[1])waste-=now[i];
now[i]+=b[rr];
}
return 0;
}
int main(){
n=read(n);
for(int i=1;i<=n;i++)a[i]=read(a[i]),sum+=a[i];
m=read(m);
for(int i=1;i<=m;i++)b[i]=read(b[i]);
sort(b+1,b+m+1);
for(int i=1;i<=m;i++)qz[i]=qz[i-1]+b[i];
int l=1,r=m;
while(l<=r){
waste=0;
for(int i=1;i<=n;i++)now[i]=a[i];
mid=(r-l)/2+l;
if(check(mid,1))l=mid+1;
else r=mid-1;
}
printf("%d\n",r);
return 0;
}
```
一开始看到这个代码：哇，好强
by HeartBlock_Love @ 2019-11-11 23:13:12
@无可牵挂真巨
by 窃·格瓦拉 @ 2019-11-11 23:13:12
@[菜♂虚♂鲲](/user/216349) 别发私信，被禁了
by HeartBlock_Love @ 2019-11-11 23:13:47
@[菜♂虚♂鲲](/user/216349) 杨钧昊的代码
by HeartBlock_Love @ 2019-11-11 23:14:06
@[菜♂虚♂鲲](/user/216349) 结果，当我仔细地研究了题解后
by HeartBlock_Love @ 2019-11-11 23:14:38
fo现了这篇题解
```
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#define maxn 2005
using namespace std;
int mid;
int n,m;
int mouth[maxn],cake[maxn];
int tot=0,space;
int sum[maxn],fcake[maxn];
int cmp(const void *a, const void *b)
{
return(*(int *)a-*(int *)b);
}
bool dfs(int deep,int pos)
{
if(deep<=0)return 1;
if(tot-space<sum[mid])return 0;//¼ôÖ¦
//dfsʱ¼Ç¼µ±Ç°À˷ѵĵ°¸âºÍ
//×ܵ°¸âÁ¿-µ±Ç°À˷ѵĵ°¸âºÍ<µ±Ç°¶þ·ÖµÄÒªÂú×ãµÄ×ì´óСºÍ
//¾Í˵Ã÷ÎÞ·¨Âú×㣬ÔòÍ˳ö¡£
for(int i=pos;i<=n;++i)
{
if(fcake[i]>=mouth[deep])
{
fcake[i]-=mouth[deep];
if(fcake[i]<mouth[1]) space+=fcake[i];
if(mouth[deep]==mouth[deep-1]) //¼ôÖ¦
//dfsʱÈôµ±Ç°×ì°Í´óСÓëÏÂÒ»¸öÏàͬ£¬ÔòÏÂÒ»¸öÎÞÐè´Óµ°¸â1¿ªÊ¼Ã¶¾Ù
//Ö±½Ó´Óµ±Ç°×ì°Íö¾ÙµÄµ°¸âi¿ªÊ¼
{
if(dfs(deep-1,i)) return 1;
}
else if(dfs(deep-1,1)) return 1;
if(fcake[i]<mouth[1]) space-=fcake[i];
fcake[i]+=mouth[deep];
}
}
return 0;
}
int main()
{
cin>>n;
for(int i=1;i<=n;++i)
{
scanf("%d",&cake[i]);
tot+=cake[i];
}
cin>>m;
for(int i=1;i<=m;++i)
{
scanf("%d",&mouth[i]);
}
qsort(cake+1,n,sizeof(int),cmp);
qsort(mouth+1,m,sizeof(int),cmp);
sum[0]=0;
for(int i=1;i<=m;++i)sum[i]=sum[i-1]+mouth[i];
while(sum[m]>tot)--m;//¼ôÖ¦
//ÒÔ×îСµÄ×ìÀÛ¼Ó£¬Óëµ°¸â×ܺͱȽϣ¬ÕÒµ½×î¶àÄÜÂú×ãµÄ×ìÊý£¬¾ÍÊǶþ·ÖÉϱ߽ç
int l=0,r=m;
while(l<=r)
{
mid=l+r>>1;
for(int i=1;i<=n;++i)fcake[i]=cake[i];
space=0;
if(dfs(mid,1))l=mid+1;
else r=mid-1;
}
cout<<l-1;
puts("");
return 0;
}
```
哇， 真像
by HeartBlock_Love @ 2019-11-11 23:15:34