Codeforces 1341B - Nastya and Do

打卡圣地 这有山 的书店，配合着发黄的灯光，显得那么温馨愉悦。

翻译

情人节，Denis 想要给 Nastya 一个惊喜，没有比在长度为 k 的门上画个巨大的心更好的礼物了。Nastya 非常抵触这个礼物，所以她决定把门摔到山上。

山被描述成一些列从左到右的高度，a(1)，a(2)，...，a(n) ，可以保证相邻的位置不会有相同的高度。

山峰就是高度比两边高的位置，例如在 [l, r] 范围内，如果 i 满足，l < i < r, a(i-1) < a(i) and a(i) > a(i+1)，那么 i 就是山峰。

为了打碎这个门， Nastya 将长度为 k 的门扔到 [l, l + k - 1] 的山中（ps：请思考下为什么要减一）。如果门碰到山峰则会被打破成两部分，然后门会继续下落，碰到山峰会继续被打破，如此往复。门会被分成山峰的数量加1。

总的来说，你需要选择一段山，包含最大的山峰数量，如果并且保证 l 最小。

输入格式

第一行输入整数 t 表示测试用例组数。接下来输入测试用例。

第一行，输入 n 和 k 用空格分隔。

第二行，输入 n 个整数，用空格分割。

可以保证，所有的 n 的和不超过 2 * 10^5。

输出格式

每行输出两个数字，被分割的数量 和 最小位置。

分析

这道题就是计算区间内有多少山峰，如果是暴力做大概会超时。当然，我没有测试暴力写法，在脑海中否掉了这个写法，因为 n * k 的数据范围大概是 10 的 10 次方。

这里用到了滑动窗口的思路，先计算最左边 k - 1 范围的山峰数量，然后每次往右偏移 1。如果左边出去一个山峰就将总数减一，如果右边进入一个山峰，就要加一。每次偏移都要判断山峰数量是否大于目前最大山峰数量，记录好位置和最大值。

这个滑动窗口的思路与 tcp 的发送窗口，nginx 的桶思路都很相似。可以说，工作中用到的很多东西的原理，都是借助了这些基础的算法思路。

代码(PyPy3)

通过记录

细心的人可能发现，我提交的语言变成了PyPy3，我查了下它与Python3的区别，主要是它使用 Python3 写了解释器代码，也就是实现了自编译。据说，一门好的语言最后都是要自编译的，这样可以提升代码运行效率。

# https://codeforces.com/problemset/problem/1341/B

import sys

# sys.stdin = open(r"./file/input.txt", 'r')
# sys.stdout = open(r"./file/output.txt", 'w')

t = int(input())

for _ in range(t):
    arr = input().split(" ")
    n = int(arr[0])
    k = int(arr[1])

    arr = input().split(" ")
    arr = list(map(int, arr))
    isPeek = [False]
    for i in range(1, n - 1):
        isPeek.append(arr[i] > max(arr[i - 1], arr[i + 1]))
    isPeek.append(False)

    num = 0
    left = 0
    right = k
    for i in range(k - 1):
        num += (1 if isPeek[i] else 0)

    maxvalue = num
    minleft = 0
    
    for r in range(k, n):
        left += 1
        if isPeek[left]:
            num -= 1
        if isPeek[r - 1]:
            num += 1
        
        if num > maxvalue:
            minleft = left
            maxvalue = num
    
    print(maxvalue + 1, minleft + 1)

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.05.08 长春