首页 > 代码库 > 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 }
Unfold Code
  • 分析:

  虽然最大只有2e5,内存足够的情况下,max_n大一点更好,避免编程是改来改去的;

abcd[0]存放特殊元素,好处是使后续操作统一化(不必写额外语句去判断特殊情况);

数字的LL后缀代表这是一个long long型变量,1LL*int 使int变为long long(C语言基础,不同数据范围的运算,得到范围较大的类型);

最后就是二分法一定要好好写啊,考虑清楚再写,避免消耗过多时间。(这个二分法,搞了半小时....Orz);

Codeforces Round #379 (Div. 2) 总结分享