然后觉得这题方法还是很重要的。没写平衡树，用优先队列（堆）来维护，单调队列维护最大值删除元素时用vis标记一下，取优先队列首的时候判断有没有被标记过，是的话就扔掉重复此动作。
然后最左端是特例，特殊对待就行了。具体还看上面↑。
错误：很智障的把m数据类型定义为int。。结果查半天才发现是类型不对。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 #include<queue> 7 using namespace std; 8 typedef long long ll; 9 template<typename T>inline char MIN(T&A,T B){return A>B?A=B,1:0;} 10 template<typename T>inline char MAX(T&A,T B){return A<B?A=B,1:0;} 11 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 12 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 13 template<typename T>inline T read(T&x){ 14 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 15 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 16 } 17 const int N=100000+7;const ll INF=1e13; 18 struct komeiji_satori{ 19 int las,now; 20 komeiji_satori(int x=0,int y=0):las(x),now(y){} 21 }; 22 ll a[N],sum[N],f[N],m;//m!!!!long long !!! 23 int q[N],vis[N]; 24 int n,L,l=1,r=0; 25 priority_queue<komeiji_satori> minv; 26 inline bool operator <(const komeiji_satori&A,const komeiji_satori&B){ 27 return f[A.las]+a[A.now]>f[B.las]+a[B.now]; 28 } 29 inline ll getans(){ 30 while(!minv.empty()){ 31 int las=minv.top().las,now=minv.top().now; 32 if(vis[now])minv.pop(); 33 else return f[las]+a[now]; 34 } 35 return INF; 36 } 37 38 int main(){//freopen("test.in","r",stdin);freopen("tmp.out","w",stdout); 39 read(n),read(m); 40 for(register int i=1;i<=n;++i){ 41 read(a[i]);sum[i]=a[i]+sum[i-1]; 42 if(a[i]>m)return printf("-1\n"),0; 43 } 44 for(register int i=1;i<=n;++i){ 45 while(sum[i]-sum[L]>m)++L; 46 while(l<=r&&a[q[r]]<=a[i])vis[q[r--]]=1; 47 q[++r]=i; 48 while(l<=r&&q[l]<=L)vis[q[l++]]=1; 49 vis[q[l]]=1; 50 if(l<r)minv.push(komeiji_satori(q[r-1],q[r]));//attention. 51 f[i]=_min(getans(),f[L]+a[q[l]]); 52 } 53 printf("%lld\n",f[n]); 54 return 0; 55 }