题解 | #立希喂猫#

立希喂猫

提供一个c++的代码，轻喷。

关于思路可以参考上面Python同学的讲解，主要用到了前缀和，降低复杂度。

不过c++的处理要麻烦一些。

下面是代码

#include<bits/stdc++.h>
#define lli long long int
using namespace std;
const int N = 1e5 + 10;

int a[N];
vector<pair<int,int> >b;

lli c[N];
lli d[N];

bool paircom(int a, pair<int,int> b){
    return a < b.first;
}

int main(void){
    int n; scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    int x;
    for(int i = 0; i < n; i++){
        scanf("%d", &x);
        b.push_back({x, i});
    }
    sort(b.begin(),b.end());
    
//     # b[i].first < k, 即全部吃完的种类
    for(int i = 0; i < n; i++){
        if (i==0) c[i] = b[i].first * a[b[i].second];
        else c[i] = c[i-1] + b[i].first * a[b[i].second];
    }
    
//     # b[i].first >= k, 没有全部吃完的种类， 只能吃k*a[-]
    for(int i = n-1; i >= 0; i--){
        if (i==n-1) d[i] = a[b[i].second];
        d[i] = d[i+1] + a[b[i].second];
    }

    
    int q; scanf("%d", &q);
    while(q--){
        lli k; scanf("%lld", &k);
        lli ind = upper_bound(b.begin(), b.end(), k, paircom) - b.begin();
        lli ans = 0;
        if (ind >= 1) ans += c[ind-1];
        ans += k*d[ind];
        printf("%lld\n", ans);
    }
    return 0;
}