题目描述
blablabla
样例
blablabla
算法1 单调队列
$O(nlogn)$
用了STL——multiset代替优先队列,懒惰删除的优先队列也是可以做的
参考文献
C++ 代码
//维护A递减的单调队列,和f[j]+max(A[k])(队列中下一个元素的A值)作为比较依据的平衡树
#include<bits/stdc++.h>
using namespace std;
#define go(i,a,b) for(int i=a;i<=b;++i)
#define com(i,a,b) for(int i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define int long long
const int inf=0x3f3f3f3f,N=1e5+10;
int a[N],q[N],f[N],sum[N];
multiset<int>s;
signed main(){
//freopen("input.txt","r",stdin);
int n,m;
cin>>n>>m;
go(i,1,n){
scanf("%lld",a+i);
sum[i]=sum[i-1]+a[i];
if(a[i]>m){
puts("-1");
return 0;
}
}
int l=1,r=0,k=0;
go(i,1,n){
while(sum[i]-sum[k]>m) ++k;
while(l<=r&&q[l]<=k){
if(l<r) s.erase(f[q[l]]+a[q[l+1]]);
++l;
}
while(l<=r&&a[q[r]]<=a[i]){
if(l<r) s.erase(f[q[r-1]]+a[q[r]]);
--r;
}
q[++r]=i;
if(l<r) s.insert(f[q[r-1]]+a[i]);
int temp;
if(!s.empty()) temp=*s.begin();
else temp=LONG_LONG_MAX;
f[i]=min(temp,f[k]+a[q[l]]);
}
cout<<f[n];
return 0;
}