[CCPC 2024 哈尔滨站] 新能源汽车 题解

Blue_Fish_Junly · 2025-12-22 13:33:55 · 题解

题目保证了 \sum n,m \le 2 \times 10^5，所以直接思考 \mathcal{O}(n\log n) 的思路。

到一个加电站时，明显应该加满。车唯一可以决定的是其走一公里时电瓶消耗的选择，因此应当考虑这个策略。既然车子不能修改加电站的电瓶编号选择，所以应当先使用下一个加油站所支持的电瓶。

整理下来就是这样：

• 如果没有电量，说明就到此为止；
• 如果有电量但接下来没有加电站，就随便耗完所有的电。
• 否则，观察自己接下来需要碰到的加电站，定义其编号为 k \sim m 号。从 k 号加电站一直往后扫，如果扫到的加电站能够填满的电瓶还有电量，就耗掉这些电量；否则，继续扫到下一个加电站。

考虑用 set 维护所有的电瓶，并以能够充该电瓶的最近加电站为关键字排序，每次取出顶部即可。另一种普适性做法是使用堆维护，原理几乎一致，不过 set 更易于实现和理解，故这里使用了 set，其时间复杂度为 \mathcal{O}(m \log n)。

:::success[代码]

#include<iostream>
#include<set>
#include<algorithm>
using ll=long long;
using std::set;
char ch;
inline char gc() {
    static char buf[1<<18],*p1=buf,*p2=buf;
    if(p1==p2) {
        p2=(p1=buf)+fread(buf,1,1<<18,stdin);
        if(p1==p2) return EOF;
    }
    return *p1++;
}
template<typename _Tp>
inline void read(_Tp& x) {
    x=0;
    while((ch=gc())<48);
    do x=(x<<3)+(x<<1)+(ch^48);
    while((ch=gc())>47);
}
template<typename _Tp>
inline void write(_Tp x) {
    if(x>9) write(x/10);
    putchar((x%10)^48);
}
int T,n,m,x[100002];
ll a[100002],t[100002];
struct node {
    ll bott,nxt;
    inline bool operator < (const node &y) const{
        return nxt<y.nxt;
    }
};
set<node> st;
ll lst[100002],pk[100002],now[100002];
void solve() {
    read(n), read(m);
    for(int i=1; i<=n; i++) read(a[i]);
    for(int i=1; i<=m; i++) read(x[i]), read(t[i]);
    for(int i=1; i<=n; i++) pk[i]=m+i,now[i]=a[i];
    for(int i=m; i>=1; i--) {
        lst[i]=pk[t[i]];
        pk[t[i]]=i;
    }
    st.clear();
    for(int i=1; i<=n; i++) st.insert((node) {i,pk[i]});
    x[m+1]=2e18;
    ll pos=0;
    for(int i=1; i<=m+1; i++) {
        while(pos<x[i] and !st.empty()) {
            node tis=*(st.begin());
            if(now[tis.bott]>x[i]-pos) {
                now[tis.bott]-=x[i]-pos;
                pos=x[i];
            } else {
                pos+=now[tis.bott];
                now[tis.bott]=0;
                st.erase(st.begin());
            }
        }
        if(pos!=x[i]) break;
        if(i!=m+1) {
            if(st.find({t[i],i})!=st.end()) st.erase(st.find((node){t[i],i}));
            now[t[i]]=a[t[i]];
            st.insert((node) {t[i],lst[i]});
        }
    }
    write(pos);
    putchar('\n');
}
int main() {
    read(T);
    while(T--) solve();
    return 0;
}

:::