题目描述

给定一个数组$a_1,a_2,a_3,...,a_n$ ， 你每次可以对数组任意一个正整数进行-1操作。问最少多少次使得其所有长度为$x$的子数组的和 $\leq$ $y$。

输入描述

第一行，两个整数 $x , y(1\leq x \leq 10,0\leq y\leq 1000)$

第二行输入一个整数 $n (1 \leq n \leq 1e5)$，代表数组的大小。

第三行输入 $n$ 个非负整数表示数组 $a$ ，第 $i$ 个数为 $a_i(0 \leq a_i\leq 10^5)$ 。

输出描述

一个整数，代表最少操作次数。

样例

输入

2 4
4
1 3 3 3

输出

2

一种方案是最终改成:1 3 1 3 , 把第三个位置的数从3改成1。花费两次操作

输入

2 6
4
1 3 3 3

输出

0

所有长度为2的子数组([1,3],[3,3],[3,3])的和都小于等于6,所以无需操作

题面描述

给定一个数组，你可以对任意正整数进行减一操作，目标是使得所有长度为 (x) 的子数组的和不超过 (y)。输入包括数组的长度 (n)、子数组长度 (x)、限制值 (y) 以及数组本身，输出最少需要的操作次数。通过示例可知，合理修改数组中的元素可实现目标，有时可能无需任何操作。

思路：贪心

从前往后依次枚举每个长度为$m$的区间，如果当前区间和不满足条件，按照贪心的思想考虑，则应该优先减少当前区间的最后一个元素，这样可以使得后面区间操作次数少一些。

题解

本题要求我们对一个给定的数组进行操作，使得所有长度为 (m) 的子数组的和不超过给定的限制值 (up)。我们可以对数组中的任意正整数进行减一操作。为了有效地减少操作次数，我们采用贪心策略，优先减少当前区间的最后一个元素，这样可以在后续的区间中减少操作的需要。

具体步骤如下：

1. 首先，我们遍历每个长度为 (m) 的子数组。
2. 对于每一个子数组，如果它的和大于 (up)，我们需要进行调整。
3. 从子数组的最后一个元素开始检查，优先减少这个元素的值，直到子数组的和不再超过 (up)。
4. 在减少元素的同时，我们记录所需的操作次数。
5. 为了维护滑动窗口的效果，更新当前子数组的和，并准备进入下一个子数组的检查。

这种贪心策略确保了每次调整都尽可能地减少未来可能需要的操作，从而提高了效率。

时间复杂度

$O(n)$

代码

C++

#include<bits/stdc++.h>
using namespace std;

#define int long long // 定义 long long 为 int，以便后续操作中使用更大的数字范围

signed main() {
    int m, up; // m: 子数组长度, up: 子数组和的上限
    cin >> m >> up; // 输入 m 和 up
    int n; // 数组的大小
    cin >> n; // 输入数组的大小
    vector<int> a(n); // 初始化数组
    for (int i = 0; i < n; i++) cin >> a[i]; // 输入数组的元素

    // 特殊情况处理：如果 m 为 0 或者 m 大于 n，则无需操作，直接输出 0
    if (m == 0 || m > n) {
        cout << 0 << endl;
        return 0;
    }

    int sum = 0, ans = 0; // sum: 当前子数组的和, ans: 总操作次数
    // 先计算前 m-1 个元素的和
    for (int i = 0; i < m - 1; i++) {
        sum += a[i];
    }    

    // 从第 m-1 个元素开始遍历到最后一个元素
    for (int i = m - 1; i < n; i++) {
        sum += a[i]; // 计算当前子数组的和

        // 从当前子数组的最后一个元素向前检查
        for (int j = i; j >= i - m + 1; j--) {
            // 如果当前子数组的和满足条件，跳出循环
            if (sum <= up) {
                break;
            }
            // 如果去掉 a[j] 后的和仍然满足条件，则减小 a[j]
            if (sum - a[j] <= up) {
                a[j] -= sum - up; // 减少 a[j]
                ans += sum - up; // 记录操作次数
                sum = up; // 更新当前和为上限
            } else {
                // 如果去掉 a[j] 后仍不满足条件，则将 a[j] 减为 0
                sum -= a[j]; // 更新和
                ans += a[j]; // 记录操作次数
                a[j] = 0; // 将 a[j] 置为 0
            }
        }
        // 更新 sum，为下一个滑动窗口做准备
        sum -= a[i - m + 1]; 
    }
    cout << ans << endl; // 输出总操作次数
    return 0;
}

python代码

# 输入 M 和 N，分别表示请求窗口的大小和最大请求总量
M, N = map(int, input().split())
# 输入 X，表示请求的总数
X = int(input())
# 输入 requests 列表，存储所有请求的数量
requests = [int(c) for c in input().split()]

r = M  # 初始化 r 为 M，表示当前窗口的右边界
res = 0  # 初始化 res 为 0，用于记录总共减少的请求数量

# 当窗口的右边界 r 小于等于总请求数 X 时进行循环
while(r <= X):
    # 获取当前窗口的请求数量（从 r-M 到 r-1 的请求）
    window = requests[r-M:r]
    # 计算当前窗口的请求总量
    total_requests = sum(window)

    # 如果当前窗口的请求总量超过了最大请求限制 N
    if total_requests > N:
        # 计算需要减少的请求数量
        to_remove = total_requests - N
        res += to_remove  # 增加到结果中，记录总共减少的请求数量
        
        # 从当前窗口的最后一个请求开始逐个检查，优先减少后面的请求
        for i in range(r-1, r-M-1, -1):
            # 如果需要减少的请求数量大于当前请求数量
            if to_remove > requests[i]:
                to_remove -= requests[i]  # 减去当前请求数量
                requests[i] = 0  # 将当前请求数量设为 0
            else:
                # 否则，将当前请求数量减少到所需的数量
                requests[i] -= to_remove
                break  # 减少操作完成，退出循环

    r += 1  # 移动窗口的右边界到下一个位置

# 输出最终减少的请求总数量
print(res)

Java代码

import java.util.*; // 导入所有的工具类

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 创建一个 Scanner 对象用于输入
        int x = sc.nextInt(); // 输入子数组的长度 x
        int y = sc.nextInt(); // 输入子数组和的最大值 y
        int n = sc.nextInt(); // 输入数组的大小 n

        long[] a = new long[n]; // 初始化一个长度为 n 的长整型数组
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt(); // 输入数组的元素
        }

        long res = 0; // 初始化结果 res，用于记录总共减少的操作次数

        // 遍历每个可能的长度为 x 的子数组
        for (int i = 0; i <= a.length - x; i++) {
            long sum = 0; // 初始化当前子数组的和

            // 计算当前子数组的和
            for (int j = i; j < i + x; j++) {
                sum += a[j]; // 累加子数组中的元素
            }

            // 如果当前子数组的和大于 y
            if (sum > y) {
                res += sum - y; // 增加需要减少的数量到结果中
                long last = sum - y; // 需要减少的最后数量
                int j = i + x - 1; // 设置指向当前子数组最后一个元素的指针

                // 从后往前减少请求，优先减少后面的元素
                while (j >= i) {
                    // 如果当前元素大于或等于需要减少的数量
                    if (a[j] >= last) {
                        a[j] -= last; // 减少当前元素的值
                        break; // 结束当前循环
                    } else {
                        // 否则，将当前元素减为 0，并更新 last
                        last -= a[j]; // 更新剩余需要减少的数量
                        a[j] = 0; // 将当前元素设为 0
                        j--; // 移动到前一个元素
                    }
                }
            }
        }
        
        // 输出总共减少的请求数量
        System.out.println(res);
    }
}