2023美团春招4.8 后端真题和解析 第三题：水果打包

ps：题目均由网友口述提供，禁止商用。

题目名字：水果打包

小美不干外卖配送了，转行开了一家水果店。
一天她接到了一个大单，客户订购了n个水果，并且要求打包成多个果篮，一个果盛最多裝m个水果。
为了包装方便，水果按从1到n编号、同一个果籃里装的水果编号必须是连续的。果篮的成本与容积成线性关系。为了估计容积，小美简单地用样本中点估计了一下。具体来说，假设一个果篮中装的最大的水果体积是u，最小的是v，那么这个果篮的成本就是k*floor((u+v)/2) +s，其中k是果篮中装入水果的个数，s是一个常数，floor(x) 是下取整函数。
客户并没有规定果篮的数量，但是希望果篮的成本越小越好，毕竟买水果就很费了。请求出小美打包这口个水果所用的最小花费。

输入描述

第一行三个正整数n,m,s。
第二行n个正整数表示aia_iai​，表示每个水果的体积。
对于全部数据，1≤n≤1041 \\leq n \\leq 10^41≤n≤104，1≤m≤1031 \\leq m \\leq 10^31≤m≤103，$m\le n$，1≤ai,s≤1041 \\leq a_i,s \\leq 10^41≤ai​,s≤104。

输出描述

输出一个整数表示答案。

样例

输入：
6 4 3
1 4 5 1 4 1输出：
21

思路：

动态规划来解决问题。定义 $dp[i]$ 表示处理前$i$ 个水果时所需的最小花费。我们需要计算 $dp[n]$，即处理所有水果所需的最小花费：
首先，初始化 DP 数组，将所有 dp[i] 设置为 Integer.MAX_VALUE，表示最初没有找到任何合适的解决方案。我们将 dp[0] 设置为 0，因为没有水果时的花费为 0。

对于每个水果 i（1 到 n），我们需要找到一个最优解。我们将尝试将前 i 个水果放入连续的果篮，每个果篮中的水果数量不能超过 m。

我们将从水果 i 开始，向前查找 j（j 从 i-1 到 0），并检查 i 和 j 之间的水果数量是否不超过 m。如果不超过 m，则我们可以将这些水果放入一个果篮中。

对于每个可能的 j，我们需要计算这个果篮的成本。这可以通过找到这个范围内的最小体积和最大体积的水果，然后根据公式 ((maxVolume + minVolume) / 2) * (i - j) + s 来计算。

在计算了当前果篮的成本之后，我们可以将它与已经找到的解决方案（在 dp[j] 中存储）结合起来，然后更新 dp[i] 为这两者之和的较小值。这意味着我们正在寻找在包含当前果篮的情况下的最小花费。

在完成所有 i 的迭代之后，dp[n] 将包含处理所有水果所需的最小花费。

这样的话确保了同一个果篮中装的水果是连续的，并且每个果篮中的水果数量不超过 m。

代码

C++版本

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>using namespace std;int minCostToPackFruits(int n, int m, int s, vector<int>& volumes) {vector<int> dp(n + 1, INT_MAX);dp[0] = 0;for (int i = 1; i <= n; i++) {int minVolume = volumes[i - 1];int maxVolume = volumes[i - 1];for (int j = i - 1; j >= 0 && (i - j) <= m; j--) {minVolume = min(minVolume, volumes[j]);maxVolume = max(maxVolume, volumes[j]);int cost = ((maxVolume + minVolume) / 2) * (i - j) + s;dp[i] = min(dp[i], dp[j] + cost);}}return dp[n];
}int main() {int n, m, s;cin >> n >> m >> s;vector<int> volumes(n);for (int i = 0; i < n; i++) {cin >> volumes[i];}cout << minCostToPackFruits(n, m, s, volumes) << endl;return 0;
}

Java版本

import java.util.Scanner;public class Main {public static int minCostToPackFruits(int n, int m, int s, int[] volumes) {int[] dp = new int[n + 1];for (int i = 0; i <= n; i++) {dp[i] = Integer.MAX_VALUE;}dp[0] = 0;for (int i = 1; i <= n; i++) {int minVolume = volumes[i - 1];int maxVolume = volumes[i - 1];for (int j = i - 1; j >= 0 && (i - j) <= m; j--) {minVolume = Math.min(minVolume, volumes[j]);maxVolume = Math.max(maxVolume, volumes[j]);int cost = ((maxVolume + minVolume) / 2) * (i - j) + s;dp[i] = Math.min(dp[i], dp[j] + cost);}}return dp[n];}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int s = scanner.nextInt();int[] volumes = new int[n];for(int i = 0; i < n; i++) {volumes[i] = scanner.nextInt();}System.out.println(minCostToPackFruits(n, m, s, volumes));}
}

Python 版本

def minCostToPackFruits(n: int, m: int, s: int, volumes: List[int]) -> int:dp = [float('inf')] * (n + 1)dp[0] = 0for i in range(1, n + 1):minVolume = volumes[i - 1]maxVolume = volumes[i - 1]for j in range(i - 1, -1, -1):if i - j > m:breakminVolume = min(minVolume, volumes[j])maxVolume = max(maxVolume, volumes[j])cost = ((maxVolume + minVolume) // 2) * (i - j) + sdp[i] = min(dp[i], dp[j] + cost)return dp[n]if __name__ == '__main__':n, m, s = map(int, input().split())volumes = list(map(int, input().split()))print(minCostToPackFruits(n, m, s, volumes))