题目

可乐有一个很经典的活动:四个瓶盖可以换一瓶可乐.现在蒜头君一共想喝 n瓶可乐,一瓶可乐需要 m 元,请问他最少需要花多少钱?他不可以向别人借瓶盖.

输入格式 第一行一个整数 t,表示接下去有t 组询问.

接下去 t 行每行包含两个整数 n, m;n,m,含义如题.

输出格式 每行输出一个整数表示蒜头君最少要花的钱.

数据范围 对于 20% 的数据,t<=20,n<=50t;

对于 100% 的数据,t≤10000,0≤n≤100000000,1≤k≤200

思路

假设和x瓶可乐,加上其换的瓶盖,可以凑够n瓶可乐,那么问题就转为求这个x

x的值为(0,n],可以通过二分查找,以下是查找函数

int find(int n){ int l = 0; int r = n; int mid; //凑到的可乐瓶数 int sum; //当前瓶数 int t; while(l <= r){ mid = (l+r)/2; sum = mid; t = mid; //当瓶数大于4时 while(t >= 4){ //能换的可乐数 int a = t/4; sum += a; //换完后剩余的瓶数 t -= 4*a; //加上换来的瓶数 t += a; } if(sum < n){ l=mid+1; }else if(sum > n){ r=mid-1; }else{ return mid; } } }