8.2小结

纳努克，我为你带来烩面了（救世主音（bushi））

T638471 小梦的su7

一看到这道题，就感觉与前年j组某题十分相似啊，于是我选择了贪心，啊然后在20分钟的左右脑搏击术训练之后，也是写出来一份代码 然后WA了65分。。。 唔，ばか野郎！ (气出家乡话了)

额，自己看吧

问题分析

电池： 𝑛 n 个电瓶，初始电量为 𝑎 𝑖 a i ​ ，每消耗 1 单位电量前进 1 公里。 充电站： 𝑚 m 个充电站，第 𝑗 j 个充电站位于 𝑥 𝑗 x j ​ 公里处，仅能为第 𝑡 𝑗 t j ​ 块电池充电（电量无限）。 目标：从起点出发，只能前进不能后退，计算最远行驶距离。 贪心策略 在行驶过程中，‌优先消耗距离下一站充电站最近的电池‌。原因：电池在下一站充电站能重新充满，因此优先消耗“充电更方便”的电池，可最大化利用电量。

数据结构选择 用‌优先队列（最小堆）‌存储电池的“剩余电量”和“最近充电站位置”，保证每次取电量最小的电池优先消耗。

算法步骤 ‌初始化‌：读取电池数量 𝑛 n、充电站数量 𝑚 m，以及电池容量 𝑎 𝑖 a i ​ 。 ‌处理充电站‌：对于每个充电站 ( 𝑥 𝑗 , 𝑡 𝑗 ) (x j ​ ,t j ​ )，将其位置 𝑥 𝑗 x j ​ 存入电池 𝑡 𝑗 t j ​ 的队列（表示该电池在 𝑥 𝑗 x j ​ 处可充电）。 ‌模拟行驶‌： 对每个电池，将其当前电量和最近充电站位置存入优先队列（优先队列按“充电站位置升序”排列，确保优先消耗离充电站近的电池）。 遍历每个充电站，计算与上一站的距离 len len，然后从优先队列中‌优先消耗电量最小的电池‌： 若电池电量 ≤ len ≤len，消耗完该电池的电量，移除该电池。 若电池电量

len

len，仅消耗 len len 单位电量，电池剩余电量重新加入优先队列。 若剩余电量不足以到达当前充电站，记录剩余距离并退出循环。 ‌计算总距离‌：遍历所有电池，将剩余电量加到总距离中。

代码如下：

#include <bits/stdc++.h> using namespace std;

int main() { ios::sync_with_stdio(false); cin.tie(0);

int n, m;
cin >> n >> m;

// a[i]: 第i个电池的电量上限
// r[i]: 第i个电池的充电上限（初始为a[i]）
// x[i]: 第i个充电站的位置
// t[i]: 第i个充电站可充电的电池编号
vector<long long> a(n + 1), r(n + 1);
vector<long long> x(m + 1), t(m + 1);

// 读取电池容量
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];
}

// 优先队列：按电池的“最近充电站位置”升序排列（优先消耗离充电站近的电池）
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

// 为每个电池设置“极大位置的充电站”（保证初始时队列非空）
for (int i = 1; i <= n; ++i) {
    pq.push({1e18, i});  // 初始充电站位置设为极大值
}

// 处理充电站，更新电池的“最近充电站位置”
for (int i = 1; i <= m; ++i) {
    pq.push({x[i], t[i]});  // 当前充电站位置及对应电池
    // 弹出当前电池的最近充电站
    pair<long long, int> cur = pq.top();
    pq.pop();
    // 如果当前充电站是电池的充电站，更新电池的充电状态
    if (cur.second == t[i]) {
        // 为电池充电（电量恢复到上限）
        r[t[i]] = a[t[i]];
    }
    // 将电池的“下一个充电站”加入优先队列
    pq.push({x[i + 1], t[i]});
}

// 模拟行驶过程
long long ans = 0;
for (int i = 1; i <= m; ++i) {
    // 计算当前充电站与上一站的距离
    long long len = x[i] - (i == 1 ? 0 : x[i - 1]);
    
    // 优先消耗电量最小的电池，直到距离耗尽
    while (!pq.empty() && len > 0) {
        pair<long long, int> cur = pq.top();
        pq.pop();
        
        // 若电池电量 <= len，消耗完该电池电量
        if (r[cur.second] <= len) {
            len -= r[cur.second];
            r[cur.second] = 0;
        }
        // 否则仅消耗len电量，电池剩余电量重新加入优先队列
        else {
            r[cur.second] -= len;
            len = 0;
            pq.push({cur.first, cur.second});
        }
    }
    
    // 若剩余电量不足以到达当前充电站，记录剩余距离并退出
    if (len > 0) {
        ans += x[i] - (i == 1 ? 0 : x[i - 1]) - len;
        break;
    }
    
    // 若能到达当前充电站，给对应电池充满电
    else {
        r[t[i]] = a[t[i]];
        ans += x[i] - (i == 1 ? 0 : x[i - 1]);
    }
}

// 遍历所有电池，将剩余电量加到总距离中
for (int i = 1; i <= n; ++i) {
    ans += r[i];
}

cout << ans << endl;
return 0;

}

Fall to my name!(救世主音)