贪心
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; }