[EGOI 2024] Bike Parking / 车位分配 题解

· · 题解

题目传送门

一道贪心题。

我们想要总贡献尽可能大，贪心的，先尽可能地制造 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;
}