【洛谷P5653】基础最优化练习题 | Mrsrz's blog

贪心

题目大意：

给定数列 $a_1,a_2,\dots,a_n$，和 $w_1,w_2,\dots,w_n$，还有 $b_0,b_1,b_2,\dots,b_n$，初始 $b_0=0$。

要求构造出一个数列 $b$，满足 $b_i-b_{i-1}\in[-k,k]$ 且 $b_i\leq a_i$。并最大化 $\sum_{i=1}^n b_i\times w_i$.

求这个的最大值。

题解：

考虑 $b_i$ 与 $b_{i-1}$ 的差值 $\Delta$ 会对 $w_i\sim w_n$ 都产生影响。

即令 $\Delta b_i=b_i-b_{i-1},f_i=\sum_{j=i}^n w_j$.

那么要求最大化的就是 $\sum_{i=1}^n \Delta b_i\times f_i$，需要满足 $\Delta b_i\in[-k,k]$ 且 $\sum_{j=1}^i \Delta b_j\leq a_i$.

先不考虑 $a$ 的限制，那么我们显然对每个大于 $0$ 的 $f_i$，令 $\Delta b_i=k$，其余的 $\Delta b_i=-k$。

考虑存在 $a$ 的限制。我们从小到大依次加入 $\Delta b_i$，即当前的 $b_i$。如果超过了 $a_i$，那么我们就需要通过减少之前的 $\Delta b_i$ 来满足条件。我们显然是贪心地减少一个 $f_{i’}$ 最小的位置 $i’$ 的值。

这个可以使用堆维护，以 $f_i$ 为关键字。由于考虑到当前 $i$ 时，前 $i-1$ 个位置已经满足条件，因此减少之前的并不会产生影响。

时间复杂度 $O(n\log n)$。

Code：

#include<iostream>
#include<queue>
using namespace std;
const int N=1e6+6;
typedef long long LL;
int n,k;
LL f[N],ans;
int t[N],a[N];
struct data{
    LL d;int id;
    inline bool operator<(const data&rhs)const{return d>rhs.d;}
};
priority_queue<data>q;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int i=1;i<=n;++i)cin>>f[i];
    for(int i=n-1;i;--i)f[i]+=f[i+1];
    int suf=0;
    for(int i=1;i<=n;++i){
        t[i]=f[i]>0?k:-k;
        suf+=t[i];
        ans+=f[i]*t[i];
        if(t[i]==k)q.push((data){f[i],i});
        while(suf>a[i]){
            int id=q.top().id;q.pop();
            const int dlt=suf-a[i];
            if(dlt<=t[id]+k)t[id]-=dlt,ans-=dlt*f[id],suf=a[i];
            else suf-=t[id]+k,ans-=(t[id]+k)*f[id],t[id]=-k;
            if(t[id]>-k)q.push((data){f[id],id});
        }
    }
    cout<<ans<<'\n';
    return 0;
}