1.切蛋糕：

切蛋糕
如果数据量不大：

代码：

 #include<iostream>
using namespace std;
typedef long long ll;
const int N=500000;
int sum[N];
int a[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    int res=-2e9;
    for(int i=1;i<=n;i++){
        for(int j=i-m+1;j<=i&&j>=1;j++)
        res=max(res,sum[i]-sum[j-1]);
    }
    cout<<res<<endl;
    return 0;
}

数据量大：

代码：

#include<iostream>
using namespace std;
typedef long long ll;
const int N=500010;
ll sum[N];
int a[N];
int head,tail;
int q[N];
int d[N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    ll res=-2e9;
    for(int i=1;i<=n;i++){
       if(head<=tail&&q[head]<i-m)head++;
       res=max(res,sum[i]-d[head]);
       while(head<=tail&&d[tail]>sum[i])
       tail--;
       d[++tail]=sum[i];
       q[tail]=i;
    }

    cout<<max(res,ll(0))<<endl;
    return 0;
}

2.编程赛题

题目描述：

写信

Description

小Y同学是个母胎solo的孤寡宅男，虽然他很想不孤寡，但是他很社恐。

幸运的是，小Y同学因为社恐，所以除了喜欢打游戏，还会看各种书（当然主要是轻小说和玄幻小说，无脑爽就完事了），看多了书，中二的小Y同学就会去写一些小文章，小诗，他也因此成为了一个pljj的笔友。

小Y同学当然不想错过这个pljj，所以他准备坚持之后每天给她写信，来赢得好感。

小Y同学接下来能预测到自己未来nnn天中每天的灵感度 xix_ixi​。不幸的是，小Y同学的公司会经常要求他加班，所以小Y同学需要每连续写信不超过kkk天，就拿出一天来加班，其他时间用来写信。

他想知道，他最大可能得到的灵感是多少。因为小Y同学不是在囤灵感写信就是在加班工作，所以他想求助你来帮他解决这个问题。

本题为程序填空题，已在提交框里提供c++、java、python3的代码模板（切换语言时点击返回默认代码设置）

Input

第一行两个整数 n,kn,kn,k，表示有n(1≤n≤100000)n(1 \leq n \leq 100000)n(1≤n≤100000)天,连续写信的时间至多不超过k(1≤k≤100000)k(1 \leq k \leq 100000)k(1≤k≤100000)天

接下来nnn行,nnn个整数，xi(int范围内)x_i(int范围内)xi​(int范围内)表示每天的灵感

Output

一个整数,表示最大值
样例：10 6
7
4
1
6
2
2
9
10
1
3
结果：43

代码：

#include<iostream>
using namespace std;
const int N=1e6+10;
int q[N];
int id[N];
int hh,tt;
int a[N];
int f[N];
typedef long long ll;
int main(){

    int n,m;
    cin>>n>>m;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
    }
    for(int i=1;i<=n;i++){

        f[i]=q[hh]+a[i];
        while(hh<=tt&&q[tt]>=f[i])tt--;
        q[++tt]=f[i];
        id[tt]=i;
      if(hh<=tt&&id[hh]<i-m)hh++;

    }
    int ans=0;
    for(int i=n-m;i<=n;i++){//!!!!!!!

    ans=max(ans,sum-f[i]);
    }
    cout<<ans<<endl;
    return 0;
}

本题目非常的精妙，注意i在不同式子中的取值范围,if(hh<=tt&&id[hh]<i-m)hh++;这里一定要放在最后，至于为什么
因为最大不超过m,所以最大取值长度为m,因为i下标从1开始，所以最大可以在i=m+1处停止连续状态！！！

写信的单调队列：

该单调队列是单调递增的也就是新增进来的数一定比q[tail]的值要大，如果f[i]<q[tail]那么就删掉q[tail]
直到q[tail]<f[i]，其实这样也就是允许小元素替代大元素进来，如果没法替代，大元素就直接进来，只要
保持队列的最大容量为m+1就好。队头元素一定最小！！！！