OJ喝可乐

 

题目

可乐有一个很经典活动

四个瓶盖可以换一瓶可乐.现在蒜头君一共想喝 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;
        }
    }
}