首页 > 代码库 > hdu 3573(数学+贪心)
hdu 3573(数学+贪心)
Buy Sticks
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 868 Accepted Submission(s): 392
Problem Description
Imyourgod need 3 kinds of sticks which have different sizes: 20cm, 28cm and 32cm. However the shop only sell 75-centimeter-long sticks. So he have to cut off the long stick. How many sticks he must buy at least.
Input
The first line of input contains a number t, which means there are t cases of the test data.
There will be several test cases in the problem, each in one line. Each test cases are described by 3 non-negtive-integers separated by one space representing the number of sticks of 20cm, 28cm and 32cm. All numbers are less than 10^6.
There will be several test cases in the problem, each in one line. Each test cases are described by 3 non-negtive-integers separated by one space representing the number of sticks of 20cm, 28cm and 32cm. All numbers are less than 10^6.
Output
The output contains one line for each line in the input case. This line contains the minimal number of 75-centimeter-long sticks he must buy. Format are shown as Sample Output.
Sample Input
23 1 14 2 2
Sample Output
Case 1: 2Case 2: 3
Author
imyourgod (Special Thanks : crackerwang & Louty)
Source
2010 ACM-ICPC Multi-University Training Contest（14）——Host by BJTU
题意:需要 x 根20cm,y根 28cm,z根 32cm,问最少需要多少根 75 cm的木棍才可以都分出来?
题解:贪心的去选,先选3根的,选不了了才能选2根的,最后如果还有剩才能选一根的.
这些情况分别是
20 20 28
20 20 32
20 20 20
32 28
28 28
32 32
20
28
32
#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>#define LL long longusing namespace std;int main(){ int tcase,t = 1; scanf("%d",&tcase); while(tcase--) { int x,y,z; scanf("%d%d%d",&x,&y,&z); int ans = 0,a,b,c; if(x>=2&&y>=1){ /// 20 20 28 a = x/2,b=y; c = min(a,b); x=x-2*c,y=y-c; ans+=c; } if(x>=2&&z>=1){ ///20 20 32 a = x/2,b = z; c = min(a,b); x=x-2*c,z=z-c; ans+=c; } if(x>=3){ ///20 20 20 a = x/3; x = x%3; ans+=a; } if(y>=1&&z>=1){ ///28 32 c = min(y,z); ans+=c; y-=c; z-=c; } if(y>=2){ ///28 28 c = y/2; y = y%2; ans+=c; } if(z>=2){///32 32 c = z/2; z = z%2; ans+=c; } if(x||y||z) ans++; printf("Case %d: %d\n",t++,ans); } return 0;}
hdu 3573(数学+贪心)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。