Codeforces Round #379 (Div. 2) C. Anton and Making Potions 前缀最小值+贪心+二分搜索

Source

Codeforces Round #379 (Div. 2)

My Solution

题意：要合成n瓶要，合成每瓶药水需要的初始时间是x，并且总可以使用的法力值是s，然后有2种Spells，其中一种是可以把每瓶要的时间从x变成ai，并消耗bi点法力值；另一种是可以瞬间生成ci瓶药水，并消耗di点法力值，且ci、di是非递减的。这2种Spells分别每种最多使用其中的一个Spell。求配置这些药水需要消耗的最短的时间。

其中关于前缀最小值

按照名字，ab[i].a，ab[i].b其中a是效果(设定a越小效果越好)，b是花费(法力值)，,然后按照b为第一优先级、a为第二优先级升序排序，
然后预处理一下，搞出前缀最小值，这个时候ab[i].a表示但花费小于等于ab[i].b时所能达到的最好的效果，
O(n)预处理，O(1)查询

前缀最小值+贪心+二分搜索

这题比赛期间写挂了，尴尬⊙﹏⊙‖∣有个地方少个==的情况，有个地方< 搞成了<= (┬＿┬)，没办法以后要多注意这些细节

先预处理出前缀最小值，及先把ab按照b优先升序排列，a为第二优先级，然后预处理以后 ab[i].a表示 消耗法力值<= ab[i].b是所能达到的最好效果，把原来的x缩减为现在的ab[i].a。

然后先找出只使用第一种Spells时的最小只ans；

然后开始贪心，对于每个ci，di，nn = n - ci, ss = s - di；然后用二分搜索找出最靠右的ab[j].b <= ss的点，

然后遍历for(int j = max((LL)0, l - 10); j < min(r + 10, m); j++)维护最小值。

其中可以在二分搜索之前 ans = min(ans, nn * x); 以处理只使用第二种Spells的情况

由于ci、di是升序的且要找出尽可能靠后的ci，所以当ss == 0时continue继续往后扫，直到ss < 0的时候结束，此时ans里所储存的数据就是所求的最终答案了。

复杂度 O(nlogn)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 2e5 + 8;

struct p{
    LL a, b;
}ab[maxn];

inline bool cmp(const p &a, const p &b)
{
    if(a.b != b.b) return a.b < b.b;
    else return a.a < b.a;
}

LL c[maxn], d[maxn];


inline bool check(const LL& x, const LL& ss)
{
    if(ab[x].b <= ss) return true;  //<= else return false; } int main() { #ifdef LOCAL freopen("c.txt", "r", stdin); //freopen("c.out", "w", stdout); int T = 4; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); LL n, m, k, x, s; cin >> n >> m >> k;
    cin >> x >> s;
    for(int i = 0; i < m; i++){ cin >> ab[i].a;
    }
    for(int i = 0; i < m; i++){ cin >> ab[i].b;
    }

    for(int i = 0; i < k; i++){ cin >> c[i];
    }
    for(int i = 0; i < k; i++){ cin >> d[i];
    }



    sort(ab, ab + m, cmp);
    LL mina = ab[0].a;
    for(int i = 0; i < m; i++){
        ab[i].a = min(mina, ab[i].a);
        mina = ab[i].a;
    }

    //
    LL ans = n * x;
    for(int i = 0; i < m; i++){ if(s >= ab[i].b) ans = min(ans, n * ab[i].a);
        //WA21     if(s > ab[i].b) ans = min(ans, n * ab[i].a); 掉了个==的时候，哭(┬＿┬)
        else break;
    }


    LL xx, ss, nn;
    LL l = 0, r = m - 1, mid;
    for(int i = 0; i < k; i++){
        nn = n - c[i];
        ss = s - d[i];
        if(ss < 0) break;
        ans = min(ans, nn * x); //WA13 考虑只用第二种Spells的情况
        if(ss == 0) continue;   //之前把ss <= 0 break了，但ss == 0 是不能break而是continue
        l = 0, r = m - 1;
        while(l + 1 < r){ mid = (l + r) >> 1;
            if(check(mid, ss)) l = mid;
            else r = mid;
        }
        for(int j = max((LL)0, l - 10); j < min(r + 10, m); j++){
            if(ab[j].b <= ss){
                ans = min(ans, nn * ab[j].a);
            }
            else break;
        }

    }

    cout << ans << endl;


    #ifdef LOCAL
    memset(ab, 0, sizeof ab);
    memset(c, 0, sizeof c);
    memset(d, 0, sizeof d);
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx