CF913C Party Lemonade 题解

题目链接：CF913C Party Lemonade

题意：

新年派对少了柠檬水就不是真正的新年派对！

如往常一样，你期望有很多客人，购买柠檬水已成为一种愉快的必需品。

你最喜欢的商店以不同容量和不同价格销售柠檬水。

一瓶第 $i$ 类型的柠檬水容量为 $2^{i-1}$ 升，价格为 $c_i$ 卢布。商店中每种类型的柠檬水瓶数可以被认为是无限的。

你想购买至少 $L$ 升的柠檬水。你需要花费多少卢布呢？

输入格式：

第一行包含两个整数 $n$ 和 $L\left(1 \leq n \leq 30 ; 1 \leq L \leq 10^9\right)$ - 商店中瓶子类型的数量和所需的柠檬水数量（升）。 第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n\left(1 \leq c_i \leq 10^9\right)$ - 不同类型柠檬水瓶子的价格。

输出格式：

输出一个整数 - 为了购买至少 $L$ 升柠檬水，你需要支付的最少卢布数。

注意到如果 $2w_{i - 1} < w_i$ ，我们会用 $2w_{i - 1}$ 替代，因此可以预处理出每个 $i$ 的最小花费。

题目要求的是体积不小于 $L$ 的柠檬汁最少要多少钱，这种二维的问题还是套路地去二分钱数。

由于我们已经预处理过 $w_i$ 了，所以一定有 $2w_{i-1} \ge w_i$ ，也就是说我们只需要从大到小贪心买。

在题解区学了一个新的二分写法，挺有意思的，原理稍微讲一下吧。

每次探索的范围是 $(p,~p+2^{k+1}]$ ，如果 $p + 2^k$ 够，那就在 $(p,p + 2^k]$ 里找，否则在 $(p + 2^k, p + 2^{k + 2}]$ 里

找到最后会卡在 $(p,p+1]$ ，所以答案就是 $p + 1$ 。大概意思懂了就好（因为我也不知道这个有啥用）

时间复杂度 $\mathcal{O}(n+\log^2M)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)())

int n,L,w[31];
bool check(int x)
{
    int sum = 0;
    for(int i = 30; ~i; i--) if(x >= w[i]) { 
        sum += (1 << i); x -= w[i];
    }
    return sum >= L;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> L; cin >> w[0];
    for(int i = 1; i < n; i++) {
        cin >> w[i]; if(w[i] > w[i - 1] * 2) w[i] = w[i - 1] * 2;
    }
    for(int i = n; i <= 30; i++) w[i] = w[i - 1] * 2;
    int p = 0, k = 1; while(k) {
        // cout << "p = " << p << ',' << "k = " << k << '\n';
        if(!check(p + k)) p += k, k <<= 1; else k >>= 1;
    }
    cout << (p + 1) << '\n';
    return 0;
}