题目
可乐有一个很经典活动
四个瓶盖可以换一瓶可乐.现在蒜头君一共想喝 n 瓶可乐, 一瓶可乐需要 m 元
请问他最少需要花多少钱? 他不可以向别人借瓶盖
- 输入格式
第一行一个整数 t, 表示接下去有 t 组询问. 接下去 t 行每行包含两个整数 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;
while(l <= r){
int mid = (l + r) / 2;
// 凑到的可乐瓶数
int sum = mid;
// 当前瓶数
int 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;
}
}
}