Kabaleo Lite

题意

就是有n道菜，a[i]是每道菜可以赚的钱，−10^9≤ ai ≤10^9，b[i]是这道菜的个数，你每次只能选从1开始连续的菜，每份菜都选一个，然后问最多有多少顾客，并且顾客最多的前提下赚的钱最多是多少。

题解

先前缀和预处理一下，算一下从第1个到第i个都选一个的收益是多少。算完之后，我们按照sum[i]从大到小进行一个排序，然后按顺序进行选取，能选就选，不能就算了。我们用线段树维护一下[1,i]中b[i]的最小值，然后选取的时候修改一下区间[1,i]就好了，那么sum[i] * min(1 <= j <= i){b[j]}就是对于sum[i]的贡献。显然能服务多少个顾客是由b[1]决定的。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 7;
typedef long long LL;
LL sum[N]; int b[N];
#define rs (k << 1 | 1)
#define ls (k << 1)
struct Node {
    int id; LL val;
    friend bool operator<(Node x, Node y) {
        if (x.val == y.val) return x.id < y.id;
        return x.val > y.val;
    }
}a[N];
struct Tree {
    int l, r, dat, add;
}tree[N << 2];
void pushUp(int k) {
    tree[k].dat = min(tree[ls].dat, tree[rs].dat);
}
void build(int k, int l, int r) {
    tree[k].l = l; tree[k].r = r;
    tree[k].dat = 1e9;
    tree[k].add = 0;
    if (l == r) {
        tree[k].dat = b[l];
        return;
    }
    int m = (l + r) >> 1;
    build(ls, l, m);
    build(rs, m + 1, r);
    pushUp(k);
}
void pushDown(int k) {
    if (tree[k].add) {
        tree[ls].add += tree[k].add;
        tree[rs].add += tree[k].add;

        tree[ls].dat += tree[k].add;
        tree[rs].dat += tree[k].add;
        tree[k].add = 0;
    }
}
void change(int k, int x, int y, int val) {
    if (x <= tree[k].l && tree[k].r <= y) {
        tree[k].dat += val;
        tree[k].add += val;
        return;
    }
    pushDown(k);
    int m = (tree[k].l + tree[k].r) >> 1;
    if (x <= m) change(ls, x, y, val);
    if (y > m) change(rs, x, y, val);
    pushUp(k);
}
int ask(int k, int x, int y) {
    if (x <= tree[k].l && tree[k].r <= y) return tree[k].dat;
    pushDown(k);
    int m = (tree[k].l + tree[k].r) >> 1, ans = 1e9;
    if (x <= m) ans = min(ans, ask(ls, x, y));
    if (y > m) ans = min(ans, ask(rs, x, y));
    return ans;
}
inline void print(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        print(x / 10);
    }
    putchar(x % 10 + '0');
}
void solve(int cas) {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &sum[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
    }
    build(1, 1, n);
    for (int i = 1; i <= n; i++) {
        sum[i] += sum[i - 1];
    }
    for (int i = 1; i <= n; i++) a[i].id = i, a[i].val = sum[i];
    sort(a + 1, a + 1 + n);
    __int128 ans = 0;
    for (int i = 1; i <= n; i++) {
        int minn = ask(1, 1, a[i].id);
        ans += (__int128)a[i].val * minn;
        change(1, 1, a[i].id, -minn);
    }
    printf("Case #%d: %lld ", cas, b[1]);
    print(ans);
    printf("\n");
}
int main() {
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) solve(cas);
    return 0;
}