尺取法(小知识点,贪心)

    xiaoxiao2024-11-18  10

     给定长度为n的数列整数a0,a1,a2,a3 ..... an-1以及整数S。求出总和不小于S的连续子序列的 长度 的最小值。

    如果此刻所尺取的区间<S,那么右端点向右移,否者只要左端点向右移不<S,那么左端点就继续向右移

    其实就是贪心啦!

    实际上定义:反复的推进区间开头或者结尾,求满足条件的最小区间的方法称为尺取法。

    因为只有向右移,均摊复杂度就是0(n)

    转载请注明原文地址: https://ju.6miu.com/read-1293752.html
    最新回复(0)