决策单调性之 优先队列优化

基础最优化练习题

YSGH 有一个数 \(x\)，初值为 \(0\)。接下来 \(n\) 分钟，每分钟 YSGH 可以给 \(x\) 加上整数 \(y\)，其中 \(y \in [-k, k]\)，同时 YSGH 需要保证第 \(i\) 分钟结束时 \(x \le a_i\)。

设 \(b_i\) 为第 \(i\) 分钟结束时 \(x\) 的值，现在 YSGH 给你一个 \(n\) 个数的序列 \(w\)，你需要最大化 \(\displaystyle \sum_{i = 1}^{n} b_i w_i\)。

你只需要输出最大值即可。

输入格式

第一行两个正整数 \(n, k\)，意义同题面描述。

第二行共 \(n\) 个整数，第 \(i\) 个表示 \(a_i\)，意义同题面描述。

第三行共 \(n\) 个整数，第 \(i\) 个表示 \(w_i\)，意义同题面描述。

保证输入数据使得至少存在一个序列 \(b\) 满足条件。

对于 \(10\%\) 的数据，\(n \le 10\)，\(k \le 1\)。 对于 \(20\%\) 的数据，\(n \le 100\)。 对于 \(30\%\) 的数据，\(n \le {10}^3\)。 对于 \(50\%\) 的数据，\(n \le {10}^4\)。 另有 \(10\%\) 的数据，\(w_i \ge 0\)。 对于 \(100\%\) 的数据，\(1 \le n \le {10}^6\)，\(-{10}^6 \le w_i \le {10}^6\)，\(0 \le a_i \le {10}^8\)，\(1 \le k \le 100\)。

---

代码

/*                                                                                
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all

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

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first

// #define innt int
// #define inr int
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

#define nl dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    cerr << s << ' ';
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;

struct node{
    int w,k;
    node(){}
    node (int w,int k):w(w),k(k){};
    friend bool operator < (node a, node b) { return a.w > b.w; }//rev
    friend bool operator > (node a, node b) { return a.w < b.w; }
};

priority_queue<node> pq;
int n,K,a[N],w[N];

void solve(){
    n=rd;K=rd;
    rep(i,1,n)a[i]=rd;
    rep(i,1,n)w[i]=rd;
    per(i,n,1)w[i]+=w[i+1];
    int x=0,res=0;
    rep(i,1,n){
        if(w[i]>0)
        {
            res += K * w[i];
            pq.push(node(w[i],K<<1));
            x+=K;
        }else{
            res-=K*w[i];
            x-=K;
        }
        int c=x-a[i];
        x=min(x,a[i]);
        while(pq.size()&&c>0){
            node x=pq.top();pq.pop();
            int t=min(c,x.k);
            res-=t*x.w;
            c-=t;
            x.k-=t;
            if(x.k)pq.push(x);
        }

    }
    cout<<res<<endl;
}

signed main() {
    int T=1;
    while(T--){
        solve();
    }
    return 0;
}