题解：P13882 [蓝桥杯 2023 省 Java A] 小蓝的旅行计划

· · 题解

P13882题解

看来都在用反悔，使用我就给出一个不用反悔的贪心吧。

思路

如果去掉油量限制，那么这道题就是公路，我们直接贪就是了。那么既然他只多了一个油量限制，那么我们就只用处理油量限制了。使用我们每次将超出油量的油给去掉，便可以直接贪。

所以以下只给出多出的代码部分：

//x是需要的油，y是花费，z是加油上限
cin>>x>>y>>z;
sum-=x;
//...省略
sum+=z;
q.push(make_pair(y,z));
if(sum>m) {
    int m_=m;//需要保留的
    while(m_&&!q.empty()) {
        pair<int,int> o=q.top();
        q.pop();
        if(o.second==0)continue;
        if(o.second>=m_) {
            q2.push(make_pair(o.first,m_));
            m_-=o.second;
            break;
        } else {
            q2.push(make_pair(o.first,o.second));
            m_-=o.second;
        }
    }
    while(!q.empty())q.pop();
    while(!q2.empty()) {
        q.push(q2.top());
        q2.pop();
    }
    sum=m;
}//因为是直接贪，所以可以实时处理