错题总结

[T638471 小梦的su7](https://www.luogu.com.cn/problem/T638471?contestId=26450）

错误代码及注释

#include<bits/stdc++.h>
#define pqg(x,y) priority_queue<x,vector<x>,greater<x> >y
#define pql(x,y) priority_queue<x,vector<x>,less<x> >y
using namespace std;
long long n,m,a[1000000],x[1000000],t[1000000],sum,b=1;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(long long i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i]; // 错误1：直接累加所有电池容量，没有考虑电池的单独使用
    }
    for(long long i=1;i<=m;i++){
        cin>>x[i]>>t[i];
    }
    for(long long i=1;i<=x[m];i++){ // 错误2：逐公里模拟，效率太低，无法处理大数据
        sum--;
        if(sum==0){
            cout<<i;
            return 0;
        }
        if(i==x[b]){
            sum+=a[t[b]],b++; // 错误3：充电时直接加满，没有考虑电池的原始容量限制
        }
    }
    cout<<x[m]+sum; // 错误4：没有正确处理充电站之间的电量消耗
    return 0;
}

正确代码及注释

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define pii pair<int,int>
#define pos first
#define idx second
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
using namespace std;
const int N = 1e5 + 5;

int a[N], x[N], t[N];
int r[N]; // 保存电池的原始容量

signed main() {
    int n, m;
    cin >> n >> m;
    queue<int> yxj[n + 1]; // 每个电池对应的充电站位置队列
    priority_queue<pii, vector<pii>, greater<pii>> s; // 小根堆，存储(下一个充电位置,电池编号)
    
    // 初始化电池容量
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        r[i] = a[i]; // 保存原始容量
    }
    
    // 将充电站按电池分组
    for (int i = 1; i <= m; i++) {
        cin >> x[i] >> t[i];
        yxj[t[i]].push(x[i]); // 将充电站加入对应电池的队列
    }
    
    // 为每个电池队列添加一个极大值作为哨兵
    for (int i = 1; i <= n; i++) {
        yxj[i].push(MOD);
    }
    
    // 初始化优先队列，存储每个电池的下一个充电位置
    for (int i = 1; i <= n; i++) {
        int pos = yxj[i].front();
        yxj[i].pop();
        s.push({pos, i});
    }
    
    int ans = 0;
    for (int i=1;i<=m;i++){
        int len=x[i]-x[i-1]; // 当前段距离
        
        // 消耗电池电量来行驶这段距离
        while (len > 0) {
            if (s.empty()) break; // 没有可用电池了
            pii top = s.top();
            s.pop();
            
            if (a[top.idx] <= len) {
                len -= a[top.idx];
                a[top.idx] = 0;
            } else {
                a[top.idx] -= len;
                len = 0;
                s.push(top); // 放回剩余电量的电池
                break;
            }
        }
        
        if (len > 0){ // 电量不足以走完这段距离
            ans += (x[i] - x[i - 1] - len);
            break;
        } else{
            a[t[i]] = r[t[i]]; // 在当前充电站充满对应电池
            
            // 更新该电池的下一个充电位置
            int fi = yxj[t[i]].front();
            yxj[t[i]].pop();
            
            if(s.top().idx == t[i]) s.pop(); // 移除旧的位置
            
            s.push({fi, t[i]}); // 添加新的充电位置
            ans += x[i] - x[i - 1];
        }
    }
    
    // 加上剩余电量能走的距离
    for (int i = 1; i <= n; i++) {
        ans += a[i];
    }
    cout << ans <<'\n';
    
    return 0;
}