题目描述

猪年快乐！

在这个快乐的日子里我们当然要去超市买可乐喝啦!

现在超市有 n 种可乐，第 i 种可乐的价格为 ci，体积为 2i−1 毫升，每种可乐都是无限供应的 ，现在你想买至少 L 毫升的可乐 ，作为一个省钱小能手，聪明的你能够想到最少要花多少钱吗?

输入格式
输入包含多组测试数据。

每组数据第一行包含两个整数 n 和 L。

第二行包含 n 个数字，c1,c2,…,cn。

输出格式
每组数据输出一行结果，表示购买至少 L 毫升的可乐需要的最少花费。

输入样例

4 12
20 30 70 90
4 3
10000 1000 100 10
4 3
10 100 1000 10000

输出样例

150
10
30

思路1：完全背包

给的数据范围太大了（1e9）,放弃。

思路2：

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int N = 32;
typedef long long ll;

typedef struct Node{
    int id;
    //double rate;
    ll size;
}Node;
int n, m;
ll c[N], v[N];
Node f[N];
/*
class cmp{
public:
    bool operator () (Node a, Node b)const
    {
        return a.rate < b.rate;
    }
};
*/
bool cmp(Node a, Node b)
{
    return a.size < b.size;
}

int main()
{
    while(cin >> n >> m)
    {
        for (int i = 1; i <= n; i ++)
        {   
            cin >>c[i];
            v[i]= 1 << (i - 1);
        }

        int h = 1;
        //考虑到价格/体积 与 同体积下的价格 两种情况下的大小比较是等价的，但是除法涉及精度问题，比较麻烦。
        for (int i = n; i >= 1; i --)
        {
            f[i].id = i;
            f[i].size = c[i] * h;
            h *= 2;
        }
        sort(f + 1, f + 1 + n, cmp);

        //for (int i = 1; i <= n; i ++)
        //  cout << f[i].id << "  "  << f[i].size << endl;
        //int x;
        //cin >> x;
        ll ans = 0;
        ll res = LLONG_MAX;
        for (int i = 1; i <= n; i ++)
        {
            if (m >= v[f[i].id])
            {
                ll x = m / v[f[i].id];
                ans += x * c[f[i].id];
                m -= x * v[f[i].id];
            }
            if (m <= 0) break;
            res = min(res, ans + c[f[i].id]);
        }

        ans = min(res, ans);    
        cout << ans << endl;
    }
    return 0;
}