自动搬运

查看原文

来自洛谷，原作者为

	xvl_ 「心存迷惘，便不要击发」「但我已不再迷惘」

搬运于2025-08-24 23:01:51，当前版本为作者最后更新于2025-04-29 15:55:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

一道贪心题。

我们想要总贡献尽可能大，贪心的，先尽可能地制造 $1$ 的贡献，其次是 $0$，最后再考虑 $-1$ 的贡献。

所以我们可以直接模拟，对于期望为 $i$ 的人把他放到级别为 $j$ 的车位里，满足 $1\le j< i$ 且 $j$ 尽可能大，这些人产生的贡献为 $1$。剩下放不下的人尽量往与期望同级别的车位塞，塞不下就只能产生负贡献了。

暴力模拟是 $O(n^2)$ 的，我们发现当一个级别的车位已经空了就不再需要遍历了，于是我们可以用栈存储有剩余车位的级别。这样子时间复杂度就变为 $O(n)$ 的了。

Code

#include <bits/stdc++.h>

const long long IMX = 1ll << 30;
const long long LMX = 1ll << 60;

const long long MOD1 = 998244353;
const long long MOD2 = 1000000007;
const long long MOD3 = 1000000009;

using ll = long long;
using i128 = __int128;
using ld = long double;
using f128 = __float128;

namespace xvl_ {
    #define SP(n, x) std :: setprecision(n) << std :: fixed << x
    #define DEBUG(x) std :: cerr << #x << " = " << x << '\n'
    #define fst first
    #define snd second
    template <typename T> T Max(T a, T b) { return a > b ? a : b; } template <typename T, typename... Args> T Max(T a, Args... args) { return a > Max(args...) ? a : Max(args...); }
    template <typename T> T Min(T a, T b) { return a < b ? a : b; } template <typename T, typename... Args> T Min(T a, Args... args) { return a < Min(args...) ? a : Min(args...); }
}
using namespace std;
using namespace xvl_;
const int N = 300005;
ll n, ans;
ll a[N], b[N], cnta[N], cntb[N];
stack <int> stk;
int main() {
    // freopen("car.in", "r", stdin);
    // freopen("car.out", "w", stdout);
    ios :: sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) { cin >> a[i]; cnta[i] = a[i]; }
    for (int i = 1; i <= n; i++) { cin >> b[i]; cntb[i] = b[i]; }
    for (int i = 2; i <= n; i++) {
        stk.push(i - 1);
        while (!stk.empty() and cntb[i]) {
            if (cnta[stk.top()] >= cntb[i]) { cnta[stk.top()] -= cntb[i]; ans += cntb[i]; cntb[i] = 0; }
            else { cntb[i] -= cnta[stk.top()]; ans += cnta[stk.top()]; cnta[stk.top()] = 0; }
            if (!cnta[stk.top()]) stk.pop();
        }
    }
    for (int i = 1; i <= n; i++) {
        if (cnta[i] >= cntb[i]) { cnta[i] -= cntb[i]; cntb[i] = 0; }
        else { cntb[i] -= cnta[i]; cnta[i] = 0; }
    }
    for (int i = 1; i <= n; i++) ans -= cntb[i];
    cout << ans;
    return 0;
}