首页 > 其他 > 详细

Codeforces-Hello 2018C. Party Lemonade(贪心)

时间:2018-02-14 15:50:29      阅读:80      评论:0      收藏:0      [点我收藏+]

标签:+=   最小   ont   最小花费   main   std   ces   problem   stream   

传送门

 

N个数,代表得到2^(i-1)次幂的花费,求构造L的最小花费

 

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <algorithm>
 5 #define INF 0x3f3f3f3f
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 LL val[40];
10 bool vis[40];
11 int N;
12 LL L;
13 
14 int main() {
15     scanf("%d%lld", &N, &L);
16     val[0] = 1000000000;
17     LL tmp;
18     for (int i = 1; i <= N; i++) {
19         scanf("%lld", &tmp);
20         val[i]= min(tmp, 2 * val[i - 1]);
21     }
22     for (int i = N + 1; i <= 31; i++) {
23         val[i] = 2 * val[i - 1];
24     }
25     int high = 0;
26     LL ans = 0;
27     for (int i = 30; i >= 0; i--) {//power
28         LL tmp = 1LL << i;
29         if (L >= tmp) {
30             L -= tmp;
31             vis[i] = 1;
32         }
33     }
34     for (int i = 0; i <= 30; i++) {
35         ans = min(ans, val[i + 1]);
36         if (vis[i]) {
37             ans += val[i + 1];
38         }
39     }
40     printf("%lld\n", ans);
41     return 0;
42 }

 

Codeforces-Hello 2018C. Party Lemonade(贪心)

标签:+=   最小   ont   最小花费   main   std   ces   problem   stream   

原文:https://www.cnblogs.com/xFANx/p/8448408.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号