题意

给出个花盆 以及现在每个花盆里的泥土数然后我要把花盆里的泥土变成 现在有三种操作方式

1,将一个单位的泥土移出去消耗为

2,将一个泥土从外面移进来消耗为

3,将一个泥土从第花盆从移到第花盆消耗为

然后求总消耗的最小值

我们可以用两个大根堆来进行贪心

我们假设第个盆缺土 然后第个盆多土 那么我们先比较一下 直接往中加土更划算

还是从盆移动过来更划算

直接讲一下这个流程

以样例为讲

4 100 200 1
1 4
2 3
3 2
4 0

设第一个大根堆为储存缺土的盆 第二个大根堆为储存有多余土的盆

首先是第一个盆是缺土的 并且为空 表示只能从外面拿进来

那么我就给加上一个然后 将放入

这样处理三次 表示有三个缺土 后面如果有更优的做法 可以用更优的做法代替

然后第二个盆也是这样

到了第三个盆就是多土了

由于我们是大根堆 那么从第二个盆放进来的土会在堆顶 所以我们把堆顶拿出来 然后

相当于是 相当于去掉了一个直接加土的消耗 而选择了移动的消耗 我们一开始给加上了一个 如果没有更好的移动方式 那么我们就只能选择从外面加进来 (这里的表示第三个和第二个盆)

在上面的操作之后 我们将放入对应的大根堆中 这里的表示之前从另一个堆里拿出来的 表示存下来这一种移动方式 这一步可能不太好理解

模拟出来 假设第一个盆多土 第二个盆缺土 第三个盆多土 然后第三个转到第二个比第一个转到第二个更优

我们全部模拟出来





最后一个

算出来就表示第一个花盆选择从外面加土 然后从第二个花盆移到第三个花盆的消耗

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
priority_queue<ll> q1 , q2;        //q1存多余的 q2是少的

void solve(){
    ll n = read() , x = read() , y = read() , z = read();
    ll ans = 0;
    for(int i = 1 ; i <= n ; ++i){
        ll a = read() , b = read();
        if(a < b){        //缺土
            for(int j = 1 ; j <= b - a ; ++j){
                if(q1.empty() || i * z - q1.top() >= x){
                    //表示只能从外面拿进来 或者移动的价值大于从外面拿进来的
                    ans += x;
                    q2.push(i * z + x);
                }
                else{
                    //选择移动
                    ll t = q1.top() ; q1.pop();
                    ans += i * z - t;
                    // cout<< i * z * 2 - t <<endl;
                    q2.push(i * z * 2 - t);
                }
            }
        }
        else{
            for(int j = 1 ; j <= a - b ; ++j){
                if(q2.empty() || i * z - q2.top() >= y){
                    ans += y;
                    q1.push(i * z + y);
                }
                else{
                    ll t = q2.top(); q2.pop();
                    ans += i * z - t;
                    // cout<< i * z * 2 - t <<endl;
                    q1.push(i * z * 2 - t);
                }
            }
        }
    }
    cout<<ans<<endl;
}

int main(void){
    solve();

    return 0;
}