Codeforces Round #476 (Div. 2) [Thanks, Telegram!]

D.Single-use Stones

$\mathtt{Difficulty}$=$\mathtt{1900}$
先说结论：

最多通过的青蛙的数量就是每个长度为 $l$ 的区间中石头数量的最小值。

我们考虑一段长度为 $l$ 的区间，
因为青蛙最多跳 $l$ 的距离，
不难想到，每只青蛙都一定会在这个区间落下至少一次。
因为一定可以从另一个石子数大于等于 $n$ 的区间跳过来，
所以这样取出的答案是可行的。
那么我们就得到了结论：

最多通过的青蛙的数量就是每个长度为 $l$ 的区间中石头数量的最小值。

代码就不难写出了。

#include<bits/stdc++.h>
#define BetterIO ios::sync_with_stdio(false)
using namespace std;
int W,L,A[100001],Prefix[100001];
int main(void)
{
	BetterIO;
	register int i;cin>>W>>L;
	for(i=1;i<W;i++)cin>>A[i];
	for(i=1;i<W;i++)Prefix[i]=Prefix[i-1]+A[i];
	register int Ret(INT_MAX);
	for(i=0;i+L<W;i++)Ret=min(Ret,Prefix[i+L]-Prefix[i]);
	cout<<Ret<<endl;
	return 0;
}