题解：P14765 [ICPC 2024 Seoul R] Bottles
s23261
·
·
题解
核心思路
每个选手在路段 j 的时间区间为 [start, end]，其中 start 是选手进入路段 j 的时间，end 是离开路段 j 的时间。通过记录所有选手在每个路段的时间区间，统计每个时刻的选手数量，取最大值即为该路段所需水瓶数。
步骤实现
计算每个选手在各路段的时间区间
对每个选手 i，累计其在路段 1 到 j-1 的时间，得到进入路段 j 的 start 时间。
**收集所有路段的时间区间**
为每个路段 $j$ 创建事件列表，记录所有选手进入 $(+1)$ 和离开 $(-1)$ 的事件。
**排序事件并统计最大选手数**
按时间排序事件，相同时间的离开事件 $(-1)$ 优先于进入事件 $(+1)$。
遍历事件，实时更新当前选手数量，记录最大值。
::::success[AC代码]
```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, ans[100005], a[2005][2005];
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
for (int j = 0; j < m; j++) { // 遍历每个路段
vector<pair<int, int>> ve;
for (int i = 0; i < n; i++) { // 遍历每个选手
int st = 0;
for (int k = 0; k < j; k++) { // 计算进入路段 j 的起始时间
st += a[i][k];
}
int e = st + a[i][j]; // 离开路段 j 的时间
ve.emplace_back(st, 1); // 进入事件
ve.emplace_back(e, -1); // 离开事件
}
// 排序事件：时间升序，同时间离开事件（-1）在前
sort(ve.begin(), ve.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
if (a.first != b.first) return a.first < b.first;
return a.second < b.second; // -1 比 1 小，优先处理
});
int t = 0, mx = 0;
for (const auto& e : ve) {
t += e.second;
if (t > mx) {
mx = t;
}
}
ans[j] = mx;
}
for (int j = 0; j < m; j++) {
if (j > 0) cout << " ";
cout << ans[j];
}
cout << endl;
return 0;
}
```
::::