题解：P14765 [ICPC 2024 Seoul R] Bottles

Python_enjoy · 2025-12-15 22:38:52 · 题解

这道题需要用到前缀和与差分。

我们先用前缀和数组 t_{i,j} 来记录在什么时候选手 i 来到了第 j 段路段上，然后依次枚举每一个路段上在每一个人数发生变化的时刻，取人数的最大值作为答案。

那么我们可以怎么实现维护人数变化的功能呢？没错，差分。那么我们如何更加高效地利用空间呢？没错，map。

下面是我的代码实现：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e2;
const int M = 3e2;
int a[N + 5][M + 5], t[N + 5][M + 5], n, m;
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            t[i][j + 1] = t[i][j] + a[i][j];
        }
    }
    for (int i = 1; i <= m; i++) {
        map<int, int> d;
        for (int j = 1; j <= n; j++) {
            d[t[j][i]]++;
            d[t[j][i + 1]]--;
        }
        int peo = 0, ans = 0;
        for (auto j : d) {
            peo += j.second;
            ans = max(ans, peo);
        }
        cout << ans << " ";
    }
    return 0;
}