poj3017 Cut the Sequence[平衡树+单调队列优化]

时间:2022-05-23 21:15:15

这里已经讲得很清楚了。

然后觉得这题方法还是很重要的。没写平衡树,用优先队列(堆)来维护,单调队列维护最大值删除元素时用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 }