题目链接

https://codeforces.com/gym/105459/problem/J

思路

我们发现，从充电站$i$走到充电站$i+1$的时候，一定是用能先充电的电池，这样模拟就是$O(n^2)$。

我们可以考虑用小根堆来维护电池的使用顺序。假设我们当前在充电站$i$，对于每一块电池$j$，如果后面有充电站$k$可以为其充电，则其使用顺序的为对应的最小的$x[j]$，否则这块电池的使用顺序为$x[m]+1$。

对于从小根堆中取出的一块电池$idx$，如果不足以支撑汽车开往下一个充电站，则继续从堆中取出下一块电池。如果可以支撑汽车开往下一个充电站，则用下一个充电站为对应的电池充满电，并将这两块电池（也可能是一块）中有电的电池重新放入堆中。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 1e5 + 5;
int n, m;
int a[N], maxn[N], x[N], t[N];
bool vis[N];
map<int, int> mp;
stack<int>nxt[N];
priority_queue<pii, vector<pii>, greater<pii>> q;
void init()
{for (int i = 1; i <= n; i++){vis[i] = false;while (nxt[i].size())nxt[i].pop();}mp.clear();
}
void solve()
{cin >> n >> m;init();for (int i = 1; i <= n; i++){cin >> a[i];maxn[i] = a[i];}for (int i = 1; i <= m; i++){cin >> x[i] >> t[i];}for (int i = m; i >= 1; i--){nxt[t[i]].push(x[i]);}for (int i = 1; i <= n; i++){if (!nxt[i].size()) mp[i] = x[m] + 1;else{mp[i] = nxt[i].top();nxt[i].pop();}}for (int i = 1; i <= n; i++){q.push({mp[i], i});vis[i] = true;}int L = 1, low = 0;while (q.size() && L <= m){int dist = q.top().first;int idx = q.top().second;q.pop();vis[idx] = false;if (low + a[idx] < x[L]){low += a[idx];a[idx] = 0;}else{a[idx] -= (x[L] - low);low = x[L];a[t[L]] = maxn[t[L]];if (t[L] != idx && !vis[t[L]]){if (nxt[t[L]].size()){q.push({nxt[t[L]].top(), t[L]});nxt[t[L]].pop();}else q.push({x[m] + 1, t[L]});vis[t[L]] = true;}L++;if (a[idx]){if (dist >= x[L])q.push({dist, idx});else{if (nxt[idx].size()){q.push({nxt[idx].top(), idx});nxt[idx].pop();}else q.push({x[m] + 1, idx});}vis[idx] = true;}}}int ans = low;while (q.size()){ans += a[q.top().second];q.pop();}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}