2 solutions

  • 0
    x,y = map(int,input().split())
    n = int(input())
    a = list(map(int,input().split()))
    r = x
    res = 0
    while r<=n:
        part_a = a[r-x:r]
        if sum(part_a)>y:
            total_sum = sum(part_a)-y
            res+=total_sum
            for i in range(r-1,r-x-1,-1):
                if a[i]>=total_sum:
                    a[i]-=total_sum
                    break
                else:
                    total_sum-=a[i]
                    a[i]=0
        r+=1
    print(res)
    
    • 0
      @ 9 months ago

      题面描述

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

      思路:贪心

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

      题解

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

      具体步骤如下:

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

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

      时间复杂度

      O(n)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);
          }
      }
      
      
      • 1

      2023.10.11-秋招-第一题-塔子哥的数组操作

      Information

      ID
      63
      Time
      1000ms
      Memory
      256MiB
      Difficulty
      3
      Tags
      # Submissions
      241
      Accepted
      34
      Uploaded By