题解：CF913C Party Lemonade

ws540d · 2025-12-04 20:43:58 · 题解

题目传送门

题目简述

有重量为 2 ^ { i-1 } 的砝码，要凑一个刚好大于需求 L 的重量，每一个砝码都有价钱，求最小价值。

其中 1 \leq L \leq 10 ^ { 9 } 。

题目思想

这是一道很经典的完全背包，但事实真的是如此吗？

肯定不是， 10 ^ { 9 } 上帝来了都开不下，那么我们只能思考贪心的写法。

然后我们可以通过二进制的方法，去找到后一项是否比前一项更加便宜（两倍），然后把后一项变得更便宜，直接就可以找到了。当然还有细节，有可能转出来的二进制多于饮料的种类，特判就好了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,L;
int c[35],w[35]; 
signed main(){
    cin>>n>>L;
    c[0]=0x3f3f3f3f3f3f3f3f;
    for(int i=1;i<=n;i++){
        cin>>c[i];
        c[i]=min(c[i],2*c[i-1]);
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            c[i]=min(c[i],c[j]);
        }
    }
    for(int i=1;i<=n;i++){
        cout<<c[i]<<' ';
    }
    int ans1=0,pos=1,l=L;
    while(l){
        if(l%2==1) {
            if(pos<=n) ans1+=c[pos];
            else ans1+=((1LL<<(pos-n))*c[n]);
        }
        pos++,l/=2;
    }
    int ans2=0x3f3f3f3f3f3f3f3f;
    if((1LL<<(n))-1>=L){
        for(int i=1;i<=n;i++){
            if((1LL<<(i-1))>=L) ans2=min(ans2,c[i]);
        }
    }
    cout<<min(ans1,ans2);
}