1028: 可乐

时间限制: 1 Sec  内存限制: 128 MB

提交: 307  解决: 59

[] [] [] [命题人:外部导入]

题目描述

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

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

输入

输入包含多组测试用例。

每组测试用例第一行包含两个数字 n 和 L (1 ≤ n ≤ 30; 1 ≤ L ≤ 10⁹) ， n是可乐的种类数， L是我们最终要买的可乐体积。

第二行包含 n 个数字 C1，C2,...Cn n (1 ≤ ci ≤ 10⁹) ,代表每一种可乐的价格。

输出

输出一个数字 ， 购买至少L毫升的可乐需要的最少花费。

样例输入

4 1220 30 70 904 310000 1000 100 104 310 100 1000 10000

样例输出

1501030

来源/分类

 

 

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 using namespace std; 6 /*用贪心的思想做，尽量用单价最小的买,这里需要留意的地方是，有可能用单价最低 7 的买会出现这种情况，就是不能凑整，但是用单价低的多买一瓶有可能会比用单价高的 8 其他体积的凑整便宜，所以每次都需要进行比较，和多买一瓶进行比较*/ 9 10 struct cole{11     int v;12     int price;13     double per;14 }arr[35];15 16 bool cmp1(cole a, cole b) {17     return a.per < b.per;18 }19 20 int main(){21     int n;22     long long L;23     while (cin >> n >> L){24         for (int i = 0; i
            
             > arr[i].price;26             arr[i].v = pow(2, i);27             arr[i].per = (double)arr[i].price / arr[i].v;28         }29         sort(arr, arr + n, cmp1); 30         int j = 0;31         long long sum = 0, min=0;32         while (L>0){33             int vol = arr[j].v;34             int cost = arr[j].price;35             sum = sum + (L / vol)*cost;36             if (j == 0){
       //最开始的时候就用单价最低的价格买完，多买一瓶，保证买完37                 min = (L / vol)*cost +cost;38             }39             if (L%vol == 0){
       //恰好可以用最优的分量买完40                 if (sum < min)min = sum;41                 break;42             }43             if (sum + cost < min){
       //进行比较44                 min = sum + cost;45             }46             L = L%vol;47             j++;48         }49         cout << min << endl;50     }51     return 0;52 }