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 localfreopen("data.txt","r",stdin); #endifIOS;work();return 0; } View Code

?

轉載于:https://www.cnblogs.com/liuweimingcprogram/p/6068303.html

總結

以上是生活随笔為你收集整理的C. Anton and Making Potions 贪心 + 二分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。