首页 > 其他 > 详细

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

时间:2018-06-18 10:20:12      阅读:241      评论:0      收藏:0      [点我收藏+]

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

题目描述

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

输入描述:

第一行三个数字n, m, x(2 ≤ n,m ≤ 10
6
,1 ≤ x ≤ 10
9
)。
第二行n个数字(1 ≤ a
i
 ≤ 10
9
)。

输出描述:

输出一个操作数,代表实现要求的最少操作数。
示例1

输入

复制
3 2 3
2 1 2

输出

复制
0

说明

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


题解:尺取思想,先找出n个数中前m个数需要多少操作数,
然后再将这长度为m的滑块以每次滑动一步的操作,

更新每次滑动后所需要加的操作数,滑到最后既可以得到结果
技术分享图片
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
ll n,m,x;
ll a[maxn];
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>x;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    ll sum=0;
    for(int i=1;i<=m;i++){
        sum+=a[i];
    }
    int pos=m;
    ll ans=0;
    while(sum>x){
        ll tt=min(sum-x,a[pos]);
        a[pos]-=tt;
        sum-=tt;
        ans+=tt;
        pos--;
    }
    for(int i=m+1;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 0;
}
View Code

 



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

原文:https://www.cnblogs.com/buerdepepeqi/p/9194258.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!