24678: 任性买房

http://cs101.openjudge.cn/practice/24678/

在刚刚过去的5月20日，唐老板抽到了价值为W的买房优惠券，且该优惠券的使用条件是实际支付金额不小于W。正巧618即将来临，他希望在中关村北大街买房，经中介介绍，从南至北总共有n套房，每套房价格为pi，他有一些想法：

能用掉优惠券，多余的钱他自己能出，这样怎么想都很赚
所购买的房屋都是相邻的，这样就能够直接打通（例如在购买k套房时，购买的是i,i+1,i+2,...,i+k-1，其中i >= 1, i + k -1 <= n）
购买的房屋数量尽可能少，使得留下尽可能多的房

请你编写一个程序帮唐老板想想是否存在符合他怪异想法的方案

输入

总共两行，第一行是两个整数W和n，0 < W < 10^9, 0 < n < 10^5,中间用空格分开，分别表示优惠券的金额与房子数量；第二行是n个整数，表示第i套房的价格pi, 0 < pi < 10^5

输出

如果存在满足条件的方案，请输出购房的最小数量；如果没有，则输出0

样例输入

7 6
1 3 5 2 1 4

样例输出

使用一个滑动窗口算法。从左到右扫描一遍房价数组，同时维护一个窗口，使得这个窗口中的房价总和大于等于优惠券金额W。我们的目标是找到满足条件的最小窗口长度。

python

def min_houses_to_buy(W, n, prices):
    min_length = n + 1  # 初始化为最大长度+1，表示不可能的情况
    current_sum = 0     # 当前窗口的价格总和
    left = 0            # 窗口的左边界

    # 遍历房屋价格数组
    for right in range(n):
        current_sum += prices[right]  # 扩展窗口的右边界

        # 当当前总和大于等于W时，尝试缩小窗口的大小
        while current_sum >= W and left <= right:
            min_length = min(min_length, right - left + 1)
            current_sum -= prices[left]  # 缩小窗口的左边界
            left += 1

    # 如果min_length没有更新，说明没有找到满足条件的窗口
    return min_length if min_length <= n else 0

# 读取输入
W, n = map(int, input().split())
prices = list(map(int, input().split()))

# 计算结果并打印
print(min_houses_to_buy(W, n, prices))

24678: 任性买房 ​

24678: 任性买房