链接:https://www.nowcoder.com/acm/contest/134/H
来源:牛客网
第一行三个数字n, m, x(2 ≤ n,m ≤ 106
,1 ≤ x ≤ 109
)。i
第二行n个数字(1 ≤ a
≤ 109
)。
输出一个操作数,代表实现要求的最少操作数。
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; }
原文:https://www.cnblogs.com/buerdepepeqi/p/9194258.html