题解 P1714 【切蛋糕】

7wwwwth · 2018-10-24 15:08:08 · 题解

咦还是基本的前缀和加单调队列

但是前缀和可以不用数组来维护

在每一步读入的时候都处理就行

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;

int n,m,x,h=1,t=1,sum,ans;

struct aaa{
    int u,v;//v表示 u表示队列长度 
}q[100010];

void read(int &x){
    x=0;char c=getchar();int flag=1;
    while(c<'0'||c>'9') 
    flag=(c=='-'?-1:1),c=getchar();
    while(c>='0'&&c<='9')
    x=x*10+c-'0',c=getchar();
    x*=flag;
}

int main(){
    read(n);read(m);read(sum);
    q[t].u=1;q[t].v=sum; 
    for(int i=2;i<=n;i++){
        read(x);
        sum+=x;
        while(h<=t&&q[t].v>=sum) t--;
        q[++t].u=i;q[t].v=sum;//u 入队操作 v当前队尾值 
        while(h<=t&&q[t].u-q[h].u>m) h++;//出队操作 
        ans=max(ans,q[t].v-q[h].v);//t.v-h.v表示当前队列的值 
    }
    cout<<ans<<endl;
}