题目描述
猪年快乐!
在这个快乐的日子里我们当然要去超市买可乐喝啦!
现在超市有 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;
}