【Hello 2018 C】Party Lemonade

在这里输入题意

【题解】

处理出凑够2^j最少需要花费多少钱。
即试着把第i种物品买2^(j-i)个,看看会不会更便宜
记录在huafei[0..31]中
然后对于L;
把它转成二进制。累加二进制中对应为1的地方的对应huafei
(如果某个高位的1不加的话,肯定要用低位的来凑->但我们已经处理出来了最小的值了,肯定没有直接用huafei来的好->或者只能得到
(相同的价格。
作为初始答案。
但是可能不是这样老老实实地累加的。
因为可以超过。
则某个位置如果加了两次的话。就直接超过了。可以不用继续加了。
(不一定是为1的地方,为0的地方也可以加的

当然可能是更高位的直接只加了一个。

取最小值就好。

【代码】

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int M = 32;

ll huafei[M],L,c[M+10];

int n,a[M+10];

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

	memset(huafei,255,sizeof huafei);

    cin >> n >> L;

    for (int i = 0;i <= n-1;i++) {

        cin >> c[i];

        huafei[i] = c[i];

    }

    for (int i = 0;i <= n-1;i++){

        ll cost = c[i];

        for (int j = i+1;j <= M-1;j++){

            cost*=2;//当前的花费

            if (cost>=1e18+1) break;

            if (huafei[j]==-1 || huafei[j]>cost) huafei[j] = cost;

        }

    }

    ll now = L;

    int cnt = 0;

    while (now>0){

        cnt++;

        a[cnt] = now&1;

        now/=2;

    }

    ll cost = 0;

    for (int i = cnt;i >= 1;i--){

        int ti = i-1;

        if (a[i]){

            cost += huafei[ti];

        }

    }

    for (int i = cnt;i<M;i++)if (huafei[i]!=-1) cost = min(cost,huafei[i]);

    ll temp = 0;

    for (int i = cnt;i>=1;i--){

        int ti = i-1;

        if (a[i]){

            temp+=huafei[ti];

        }

        cost = min(cost,temp+huafei[ti]);

    }

    cout << cost << endl;

	return 0;

}

巴特西

【Hello 2018 C】Party Lemonade

最新文章

热门文章