题解：CF913C Party Lemonade

_fallen_leaves_ · 2025-06-14 16:42:47 · 题解

CF913C Party Lemonade

题意

有 n 杯柠檬汁，每杯柠檬汁的体积为 2^{i-1} 升，价格为 c_i 卢布，问你要买 L 升，最少要花多少卢布。

思路

我们知道如果 2 \times c_i \le c_{i+1} ，我们就会买 2 瓶价格为 c_i 的柠檬汁，而不是买价格为 c_{i+1} 的柠檬汁。

我们假设购买大于等于 x 件为最优解，假设购买了 y 件也为最优解，我们从 x 与 y 的二进制位从高位往低位看，如果某一位 x 与 y 的二进制位不同，我们就从这个地方找最优解。

贴代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,l,len,c[35],ans,x[35];
signed main()
{
    scanf("%d%d",&n,&l);
    while(l)
    {
        x[len++]=l&1;
        l>>=1;
    }
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&c[i]);
        if(i) c[i]=min(c[i],c[i-1]<<1);
    }
    for(int i=n;i<len;++i) c[i]=c[i-1]<<1;
    for(int i=0;i<max(n,len);i++)
    {
        ans=min(ans,c[i]);
        if(x[i]) ans+=c[i];
    }
    printf("%lld\n",ans);
    return 0;
}