SRM659 div.1 250 ApplesAndOrangesEasy
問題
SRM659 div.1 250 ApplesAndOrangesEasy
各要素がリンゴかミカンである、要素数がNの列を考える。ここで、[i, i+K-1]の区間で列に含まれるリンゴの数を個以下に制限することとする。列において、要素が必ずリンゴであるインデックスの情報infoが与えられるので、制限を満たす列でリンゴは最大何個列に含まれうるか？
制約
解法
リンゴを複数の場所に置くことができる場合、おける場所のうち先頭以外においても意味が無いことがわかる。
よって、各iについて、[i-K+1, i], [i-K+2, i+1], ..., [i, i+K-1]の各区間において、その時点でリンゴが何個含まれるか計算し、その最大値がより小さいならば、リンゴをおけばよい。
計算量
[i-K+1, i], [i-K+2, i+1], ..., [i, i+K-1]の各区間においてリンゴが何個含まれるかは、愚直に計算するとであるが、尺取法のように計算するとO(K)で求めることができる。
よって、O(NK)
