贪心
max()函数:
若有大和尚d个,馒头n个,小和尚有x=(n-d3)3个,大和尚越多,总和尚数越小。
总和尚数x+d=3n-8d<n(馒头数),根据数学计算得,n<4*d,d>n/4,所以d逐渐增加(n/4为最优解)。
根据大和尚的个数,可以得到小和尚的个数,第一个总和尚数小于馒头数的即为最优解。
min()函数:
每种和尚至少有一个(大和尚至少有一个,小和尚至少有三个),最优解为小和尚最小。
分为能整除和不能整除两种情况,保证小和尚尽可能小的情况,剩余包子能整除3,不符合返回-1。
#include<stdio.h>
typedef long long ll;
ll min(ll n){
ll x,d;
if(n%3==0){
x=9;
d=(n-3)/3;
}
else{
x=(n%3)*3;
d=(n-n%3)/3;
}
if(x+d>=n)return -1;
return x+d;
}
ll max(ll n){
if(min(n)==-1)return -1;
ll x,d;
for(d=n/4;;d++){
x=(n-d*3)*3;
if(d+x<n){
return x+d;
}
}
}
int main(){
ll t,n;
scanf("%lld",&t);
while(t--){
scanf("%lld",&n);
printf("%lld %lld\n",max(n),min(n));
}
return 0;
}
京公网安备 11010502036488号