编程技术-蓝桥 1111 第 3 场算法双周赛 深秋的苹果【算法赛】python解析

1111 第 3 场算法双周赛 深秋的苹果【算法赛】

时间：2023.11.14
题目地址： 深秋的苹果【算法赛】

题目分析

二分+前缀和。
这个代码后面两个测试点过不了，超时了只能过80%。这次比赛的数据都好奇怪，C++能过，python确过不了，不知道审核的时候是怎么审核的。
这道题跟之前的一题比较像，可以看看这道，分组 。算法都是一样的，代码我也放在了下面。

代码

① 深秋的苹果 超时代码，过80%

def check(mid):    # 判断当前的美味值是否可以满足分成组数小于等于m
    count = 1
    last = n
    total_sum = 0
    for i in range(n-1, -1, -1):
        total_sum += nums[i] * (prefix_sum[last] - prefix_sum[i+1]) # 表示数组中第 i 个元素之后所有元素的和，即数组的总和减去前 i 个元素的和。
        if total_sum > mid:
            count += 1
            if count > m:
                return False
            total_sum = 0
            last = i+1
    return True
    

n, m = map(int, input().split())
nums = list(map(int, input().split()))

# 初始化前缀和
prefix_sum = [0] * (n + 1)
prefix_sum[1] = nums[0]
for i in range(2, n + 1):
    prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]


low = 0
up = 2e18
while up > low:
    mid = (low + up) // 2
    if check(mid):
        up = mid
    else:
        low = mid + 1 
print(int(low))

② 分组， AC

def check(nums, mid):
  res = 1
  minn = maxn = nums[0]
  
  for i in range(1, n):
    minn = min(minn, nums[i])
    maxn = max(maxn, nums[i])

    if maxn - minn > mid:
      res += 1
      if res > k:
        return False
      minn = maxn = nums[i]
  return True

n, k = map(int, input().split())
nums = [int(i) for i in input().split()]

nums.sort()
lmin, lmax = 0, nums[-1] - nums[0]
while lmin < lmax:
  mid = (lmin + lmax) // 2
  if check(nums, mid):
    lmax = mid
  else:
    lmin = mid + 1

print(lmin)