牛客小白月赛4——H-相邻的糖果

链接：https://www.nowcoder.com/acm/contest/134/H
来源：牛客网

题目描述

有n个盒子摆成一排，每个盒子内都有a_i个糖果。
现在你可以执行以下操作：
·你可以选择任意一个盒子，在选择的盒子内吃掉一个糖果。
对你的要求如下：
·任何m个相邻的盒子内糖果数量不能超过x个。
请问，实现要求的最少操作次数是多少？

输入描述:

第一行三个数字n, m, x(2 ≤ n,m ≤ 10

⁶

,1 ≤ x ≤ 10

⁹

)。
第二行n个数字(1 ≤ a

 ≤ 10

⁹

)。

输出描述:

输出一个操作数，代表实现要求的最少操作数。

输入例子:

3 2 3

2 1 2

输出例子:

-->

示例1

输入

复制

3 2 3

2 1 2

输出

复制

说明

2 1 2满足题目要求，任意相邻的两个数值之和均不超过3，所以不需要进行任何操作。

题解：尺取思想，先找出n个数中前m个数需要多少操作数，
然后再将这长度为m的滑块以每次滑动一步的操作，
更新每次滑动后所需要加的操作数，滑到最后既可以得到结果

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e6+;

ll n,m,x;

ll a[maxn];

int main(){

    ios::sync_with_stdio(false);

    cin>>n>>m>>x;

    for(int i=;i<=n;i++){

        cin>>a[i];

    }

    ll sum=;

    for(int i=;i<=m;i++){

        sum+=a[i];

    }

    int pos=m;

    ll ans=;

    while(sum>x){

        ll tt=min(sum-x,a[pos]);

        a[pos]-=tt;

        sum-=tt;

        ans+=tt;

        pos--;

    }

    for(int i=m+;i<=n ;i++){

        sum+=a[i];

        sum-=a[i-m];

        if(sum>x){

            ll tt=min(sum-x,a[i]);

            a[i]-=tt;

            sum-=tt;

            ans+=tt;

        }

    }

    cout<<ans<<endl;

    return ;

}

巴特西

牛客小白月赛4——H-相邻的糖果

题目描述

输入描述:

输出描述:

输入例子:

输出例子:

输入

输出

说明

最新文章

热门文章