HDU 3573 Buy Sticks (逻辑)

题意:a,b,c三种棍子长度分别为20,28,32,现需要这三种棍子数根,欲买长为75的棍子来剪成这三种(不够长的就废弃) ,问需要买多少根。

思路:将所有棍子尽可能和其他搭配起来,使得数量减到最少。

分情况:       结果(按最坏情况考虑):

2a+c=72  要么c=0,要么a=1或a=0

2a+b=68  要么b=0,要么a=1或a=0

2c=64      c=1或c=0

b+c=60       要么c=0,要么b=0

3a=60     a=2或 a=1

2b=56     b=0或b=1

最后剩下的情况:

(1)a有很多,那么直接和b跟c搭配,全部使得b=c=0,a再跟自己搭,剩下a=1或2;

(2)a不够多,那么a可能剩下1或0(一旦有2必定跟其他搭配了),而b+c=1或0;

 #include <bits/stdc++.h>
using namespace std;
const int N=;
int a,b,c;
int cal()
{
int cnt=, tmp; tmp=min(a/,c); //要么a剩1个或完,要么c完 72
a-=tmp*;
c-=tmp;
cnt+=tmp; tmp=min(a/,b); //要么a剩1个或完,要么b完 68
a-=tmp*;
b-=tmp;
cnt+=tmp; tmp=c/; //c要么完,要么剩1 64
c-=tmp*;
cnt+=tmp; tmp=min(b,c); //c和b其中一个完 60
c-=tmp;
b-=tmp;
cnt+=tmp; tmp=a/; //a要么完,要么小于3 60
a-=tmp*;
cnt+=tmp; tmp=b/; //b要么完,要么剩1 56
b-=tmp*;
cnt+=tmp; //b可能还有一个 if(a+b+c>) return cnt+;
else if(a+b+c>) return cnt+;
return cnt;
} int main()
{
freopen("input.txt", "r", stdin);
int t, j=;
cin>>t;
while(t--)
{
scanf("%d%d%d",&a,&b,&c);
printf("Case %d: %d\n",++j,cal());
}
return ;
}

AC代码

上一篇:How to Pronounce AR, ORN, etc.


下一篇:[Kerberos] User Ticket Management