首页 > 代码库 > Codeforces Round #379 (Div. 2) 总结分享
Codeforces Round #379 (Div. 2) 总结分享
前言
初入acm的新手,打算在cf混。这几天没有比赛,就做了个最新的Virtual participation。虽然说div2比较简单,但还是被虐得体无完肤。。。Orz。两个小时,共6道题。最后只AC了AB两道,花了20分钟,剩下的100分钟也不知道哪去了(逃
A、B两道水题没什么说的。那我们从C题开始吧:
C. Anton and Making Potions
-
题意:
制作n瓶药水,初始时每制作一瓶花费x秒,有两类法术,第一类(包含m个法术)使制作每瓶药的时间由x变为a[i] (a[i] < x) 并消耗b[i]点法力值,第二种(k个法术)能瞬间制造c[i]瓶并消耗d[i]点法力值,初始法力值为s,最多在两种类型中分别选一个法术来加快进度。求制作这n瓶药水最少花费的时间。
-
思路:
暴力法肯定爆时间O(m*k),所以没敢用,就去纠结各种“巧妙”的办法,然后。。。然后时间就过去了T.T 结束之后看Tutorial,第一类就暴力,第二类在第一类的基础上二分查找,这样O(m*log2k)就不会爆了。之前从未想过二分法查找近似数(如:找到比给定值小的最大元素),这里第二类本身是有序(非递减)的,正好用二分法。
-
代码:
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 const int max_n = 1000000; 6 7 int n, m, k; 8 int x, s; 9 int a[max_n], b[max_n], c[max_n], d[max_n]; 10 11 inline int max_complete(int mana_left) 12 { 13 int l = 0, r = k; 14 while (l < r) 15 { 16 int m = (l + r + 1) / 2; 17 if (d[m] <= mana_left) l = m; else r = m-1; 18 } 19 return c[l]; 20 } 21 22 int main() 23 { 24 cin >> n >> m >> k; 25 cin >> x >> s; 26 a[0] = x; 27 b[0] = 0; 28 c[0] = 0; 29 d[0] = 0; 30 for (int i = 1; i <= m; i++) cin >> a[i]; 31 for (int i = 1; i <= m; i++) cin >> b[i]; 32 for (int i = 1; i <= k; i++) cin >> c[i]; 33 for (int i = 1; i <= k; i++) cin >> d[i]; 34 long long ans = 1LL * n * x; 35 for (int i = 0; i <= m; i++) 36 { 37 int mana_left= s - b[i]; 38 if (mana_left< 0) continue; 39 ans = min(ans, 1LL * (n - max_complete(mana_left)) * a[i]); 40 } 41 cout << ans << endl; 42 return 0; 43 }
-
分析:
虽然最大只有2e5,内存足够的情况下,max_n大一点更好,避免编程是改来改去的;
abcd[0]存放特殊元素,好处是使后续操作统一化(不必写额外语句去判断特殊情况);
数字的LL后缀代表这是一个long long型变量,1LL*int 使int变为long long(C语言基础,不同数据范围的运算,得到范围较大的类型);
最后就是二分法一定要好好写啊,考虑清楚再写,避免消耗过多时间。(这个二分法,搞了半小时....Orz);
Codeforces Round #379 (Div. 2) 总结分享