题解 CF913C 【Party Lemonade】
囧仙
2020-05-13 21:27:18
## 题目大意
$n$种柠檬汁，每种体积为$2^{i-1}$，价格为$W_i$。询问购买总体积不小于$L$的柠檬汁，最少要花多少钱。
## 题解
很显然，如果$2\times W_i<W_{i+1}$，那么我们就可以用两瓶$i$种柠檬汁来替代一瓶$i+1$种柠檬汁。这样可以保证，一次购买的体积越大，平均花费的钱越少。
让我们从一个简单的问题入手：假如你有$m$元，你**最多**能够购买到多少柠檬汁呢？
根据上述的贪心方法，我们能够发现，**尽可能购买体积更大的柠檬汁能省更多钱**。他的正确性比较容易说明。很显然，如果我们需要购买两次$i$种柠檬汁，就不如购买一次$i+1$种柠檬汁，因此每种果汁**最多购买一瓶**。如果我们放弃购买第$i$种柠檬汁，即使我们将剩下的种类都买了一遍，也达不到它的体积，甚至还要花费更多的钱。
因此，这样一个二分的算法就出来了。每次判断$x$元能否购买到$L$体积的柠檬汁，进行二分操作即可。
## 参考代码
```cpp
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=l;i>=r;i--)
using namespace std;
typedef long long LL;
const int INF =2147483647;
LL qread(){
LL w=1,c,ret;
while((c=getchar())> '9'||c< '0')
w=(c=='-'?-1:1); ret=c-'0';
while((c=getchar())>='0'&&c<='9')
ret=ret*10+c-'0';
return ret*w;
}
LL n,l,W[31],ans,p,k;
bool chk(LL x){
LL ret=0;
dn(30,0,i) if(x>=W[i]) ret+=(1<<i),x-=W[i];
return ret>=l;
}
int main(){
n=qread(),l=qread(); W[0]=qread();
up(1,n-1,i){
W[i]=qread(); if(W[i]>W[i-1]<<1) W[i]=W[i-1]<<1;
}
up(n,30,i) W[i]=W[i-1]<<1;
p=0,k=1; while(k){
if(!chk(p+k)) p+=k,k<<=1; else k>>=1;
}
printf("%lld\n",p+1);
return 0;
}
```