/*
分析:
很简单的贪心,刚开始竟然想错方向了-、-I。
假设最优方案买z条,则中lenth=z*75,实际有用的
lenth1=a*20+b*28+c*32,那么lenth-lenth1=“?”,很明
显“?”是没有用掉的,所以让“?”尽量小,就行了(因为
每根的长度是75是固定的)。
那么,贪心就行,找出三种木条关于75的组合方案,
由方案的总长度递减来增加ans就行了。再详细的见代码吧。
2012-10-12
*/
#include"stdio.h" #include"string.h" #include"stdlib.h" int min(int a,int b) { return a>b?b:a; } int main() { int T,Case; int temp; int a,b,c; int ans; scanf("%d",&T); for(Case=1;Case<=T;Case++) { scanf("%d%d%d",&a,&b,&c); ans=0; //72 temp=min(a/2,c); ans+=temp;a-=temp*2;c-=temp; //68 temp=min(a/2,b); ans+=temp;a-=temp*2;b-=temp; //2*32=64 ans+=c/2;c-=c/2*2; //28+32=60 temp=min(b,c); ans+=temp;b-=temp;c-=temp; //3*20=60 ans+=a/3;a-=a/3*3; //2*28=56 ans+=b/2;b-=b/2*2; //20+32=52 temp=min(a,c); ans+=temp;a-=temp;c-=temp; //20+28 temp=min(a,b); ans+=temp;a-=temp;b-=temp; //单 ans+=a/3+!(a%3==0); ans+=b/2+!(b%2==0); ans+=c/2+!(c%2==0); printf("Case %d: %d\n",Case,ans); } return 0; }