C. Anton and Making Potions 贪心 + 二分

http://codeforces.com/contest/734/problem/C

因为有两种操作，那么可以这样考虑，

1、都不执行，就是开始的答案是n * x

2、先执行第一个操作，然后就会得到一个time和left。就是你会得到一个新的用时，和一个剩下的魔法数，然后在第二个操作数中二分，二分第一个小于等于left的值，意思就是我现在还拥有left点魔法，能够买最多多少个技能的意思。

就是，看着样例一

得到的会是

time : 40s 80s　　60s

left : 79　　89　　 59

3、同理，可以先执行第二种操作，再执行第一种操作。这就需要我们把第一种操作的东西排序了。这里用到了贪心，排序第一是按照需要的魔法数来排，第二是按照a[i]从大到小。（这里又fst，唉，一个符号）。因为这样是最优的。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = 1e6 + 20;
LL a[maxn];
LL b[maxn];
struct node {
    LL c, d;
    node(LL cc, LL dd) : c(cc), d(dd) {}
    node() {}
    bool operator < (const struct node & rhs) const {
        return d < rhs.d;
    }
}arr[maxn];
struct tt {
    LL tim, lef;
    LL id;
}ff[maxn];
struct bug {
    LL a, b;
    int id;
    bug() {}
    bug(LL aa, LL bb) : a(aa), b(bb) {}
    bool operator < (const struct bug & rhs) const {
        if (b != rhs.b) return b < rhs.b;
        else return a > rhs.a; //这个按大排
    }
}gg[maxn];
void work() {
    LL n, m, k;
    cin >> n >> m >> k;
    LL x, limit;
    cin >> x >> limit;
    for (int i = 1; i <= m; ++i) {
        cin >> a[i];
        gg[i].a = a[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> b[i];
        gg[i].b = b[i];
        gg[i].id = i;
    }
    sort(gg + 1, gg + 1 + m);
    for (int i = 1; i <= k; ++i) {
        cin >> arr[i].c;
    }
    for (int i = 1; i <= k; ++i) {
        cin >> arr[i].d;
    }
    LL ans = n * x;
    int lenff = 0;
//    cout << x << endl;
    for (int i = 1; i <= m; ++i) {
        if (b[i] > limit) continue;
        ++lenff;
        ff[lenff].tim = n * a[i];
        ff[lenff].lef = limit - b[i];
        ff[lenff].id = i;
    }
//    for (int i = 1; i <= lenff; ++i) {
//        cout << ff[i].tim << " " << ff[i].lef << endl;
//    }
    for (int i = 1; i <= lenff; ++i) {
        ans = min(ans, ff[i].tim);
        if (ff[i].lef < arr[1].d) continue;
        int pos = upper_bound(arr + 1, arr + 1 + k, node(0L, ff[i].lef)) - arr;
        pos--;
        LL t = ff[i].tim - arr[pos].c * a[ff[i].id];
        ans = min(ans, t);
    }
    lenff = 0;
    for (int i = 1; i <= k; ++i) {
        if (arr[i].d > limit) continue;
        ++lenff;
        ff[lenff].lef = limit - arr[i].d;
        ff[lenff].tim = (n - arr[i].c) * x;
        ff[lenff].id = n - arr[i].c;
    }
    for (int i = 1; i <= lenff; ++i) {
        ans = min(ans, ff[i].tim);
        if (ff[i].lef < gg[1].b) continue;
        int pos = upper_bound(gg + 1, gg + 1 + m, bug(0, ff[i].lef)) - gg;
        pos--;
        LL t = ff[i].id * a[gg[pos].id];
        ans = min(ans, t);
    }
    cout << ans << endl;
}

int main() {
#ifdef local
    freopen("data.txt","r",stdin);
#endif
    IOS;
    work();
    return 0;
}

View Code

C. Anton and Making Potions 贪心 + 二分

相关推荐