首页 > 代码库 > [ CodeVS冲杯之路 ] P2456
[ CodeVS冲杯之路 ] P2456
不充钱，你怎么AC？
题目：http://codevs.cn/problem/2456/
用贪心的思想，木材当然要尽量分成多的木板，而大的木材能够分成大木板，但是小的木材不一定能够分成大的木板，所以木板和木材都是从小到大开始选，然后要保证剩余的木材最少
那么将木板和木材排序，对于每个木材，把能够分的小木板尽量分掉，如果遇到更大的木板则把最小的木板腾出来，然后在加上，这样保证剩余的木材最少
因为是上午写得这道题，思路可能不连贯了，代码应该描述的很清楚
虽然贪心在CodeVS上可以过，但是它是有数据可以卡掉的，而正解是DFS
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 9 const int N=51,M=1024;10 int a[N],b[M],next[M];11 bool f[M];12 int main()13 {14 int n,i,j,m,k,now,ans=0,x,y;15 scanf("%d",&n);16 for (i=1;i<=n;i++) scanf("%d",&a[i]);17 sort(a+1,a+1+n);18 scanf("%d",&m);19 for (i=1;i<=m;i++) scanf("%d",&b[i]);20 sort(b+1,b+1+m);21 for (i=1;i<=n;i++)22 {23 now=a[i];24 for (j=0;j<=m;j++) next[j]=0;25 for (j=1;j<=m;j++)26 {27 if (f[j]) continue;28 if (now>=b[j])29 {30 now-=b[j];31 f[j]=1;32 ans++;33 next[j]=next[0];34 next[0]=j;35 }36 else37 {38 k=x=0;39 while (now+b[next[k]]>=b[j]) k=next[x=k];40 if (k)41 {42 next[x]=next[k];43 f[k]=0;44 f[j]=1;45 next[j]=next[0];46 next[0]=j;47 now+=b[k]-b[j];48 }49 }50 }51 }52 printf("%d\n",ans);53 return 0;54 }
下面是DFS的正解，贴的别人的代码
1 #include<algorithm> 2 #include<iostream> 3 #include<cstdlib> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 9 #define N 110010 11 int n,m;12 int sum1,ans;13 int tim,res;14 15 int a[N],b[N],c[N],sum[N];16 17 int work(int x,int k)18 {19 if (!x)20 return true;21 if (tim>res)22 return false;23 for (int i=k;i<=n;i++)24 if (a[i]>=b[x])25 {26 a[i]-=b[x];27 if (a[i]<b[1])28 tim+=a[i];29 if (b[x]==b[x-1])30 {31 if (work(x-1,i))32 return true;33 }34 else if (work(x-1,1))35 return true;36 if (a[i]<b[1])37 tim-=a[i];38 a[i]+=b[x];39 }40 return false;41 }42 43 int main()44 {45 scanf("%d",&n);46 for (int i=1;i<=n;i++)47 scanf("%d",&a[i]),sum1+=a[i],c[i]=a[i];48 scanf("%d",&m);49 for (int i=1;i<=m;i++)50 scanf("%d",&b[i]);51 sort(a+1,a+n+1);52 sort(b+1,b+m+1);53 for (int i=1;i<=m;i++)54 sum[i]=b[i]+sum[i-1];55 int l=0,r=m;56 while (l!=r)57 {58 int mid=(l+r+1)>>1;59 tim=0;60 res=sum1-sum[mid];61 if (work(mid,1))62 l=mid;63 else64 r=mid-1;65 for (int i=1;i<=n;i++)66 a[i]=c[i];67 }68 printf("%d\n",l);69 return 0;70 }
[ CodeVS冲杯之路 ] P2456
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。