题目描述

小红现在在快递公司干活，现在公司有一个要求，当天下发的快递最迟明天要送到。

假设现在已经知道了接下来n天每天会下发的快递重量，小红要用快递车运输给客户，每一辆运输车最大只能装k重量的快递

每一天可以出多次车也可以不出车，不要求将车装满，当天的快递，最晚留到第二天就要送走。

小红希望出车次数最少，完成接下来$n$天的快递运输

输入描述

输入第一行包含两个整数$n(1 \leq n \leq 200000)$，$k(1 \leq k \leq 100000000)$

第二行包含$n$个整数$a[i].(0 \leq a[i] \leq 100000000)$表示第$i$天下发到快递中转站的快递重量

输出描述

输出最少需要的出车次数。

样例

输入

3 2
3 2 1

输出

3

解释

第一天的快递出车一次送走$2$个重量，留$1$个重量到第二天。

第二天送走第一天留下的$1$个重量和前的$1$个重量，留$1$个重量到第三天送走。

样例2

输入

3 2
1 0 1

输出

2

解释

第一天或者第二天出车一次送走$1$个重量，第三天出车一次送走$1$个重量。

题面描述

塔子哥需要在快递公司按时送达快递，为此他要有效利用运输车。每天接收的快递重量加上前一天未送达的快递重量必须在第二天送完。他可以根据运输车的最大承重来决定出车的次数，最终目标是用最少的出车次数完成所有快递的运输。通过模拟每天的快递接收和运输过程，塔子哥可以计算出所需的最小出车次数。

思路:贪心

如果第$i$天正好能够装完货物，那么我们直接当天运走。但是如果当第$i$天有剩余，我们可以尝试将它们留到下一天运走。

这样做的好处是可能可以让本来需要运两趟的变成一趟。

例如:4 2

3 1 1 1

第一天运送一批，剩下的一个留到第二天。

第二天运送一批

第三天的一个留到第四天

第四天运送一批

思路解析

1. 运输车的容量： 每辆运输车的最大承重为 k。这意味着每次出车时，塔子哥可以选择运输最多 k 单位的快递。

2. 每日快递处理： 对于第 i 天的快递重量 a[i]，需要考虑以下情况：

   • 如果当天的快递 a[i] 加上前一天留下的未送达快递（记为 carry）恰好能够被 k 整除，那么塔子哥可以当天直接出车，将所有的快递送出，不留任何剩余。
   • 如果当天的快递和前一天的未送达快递总和大于 k，则需要计算出车的次数，将多余的快递留到下一天运输。
   • 如果当日快递量加上前一天未送达的快递重量正好为 k，则当日可以完全装车。

3. 余留快递的处理： 如果第 i 天在运输后还有剩余的快递（即总重量未满 k），这部分未送达的快递可以被保留到第 i+1 天运输。这是优化的关键，因为通过将未送达的快递留到下一天，可以将本来需要两次运输的情况合并为一次运输，从而减少总的出车次数。

具体实现步骤

以下是实现该思路的详细步骤：

1. 初始化：

   • 设置 carry 为 0，表示前一天未送达的快递重量。
   • 设置 trips 为 0，用于记录出车的次数。

2. 遍历每一天：

   • 对于每一天的快递 a[i]，将其加到 carry 中。
   • 计算当前需要运输的总重量（carry）。
   • 计算当天需要的出车次数，这可以通过 (carry + k - 1) // k 来实现，这样可以向上取整。
   • 更新 carry 为运输后剩余的快递重量（carry % k）。

3. 输出结果：

   • 最终输出总的出车次数 trips。

代码

python

# n:货物数量 k:运输量
n , k = map(int, input().split()) 
# arr:货物重量
arr = list(map(int, input().split())) 
# cnt:运输次数
cnt = 0 
# rest:剩余的货物
rest = 0 
for i in range(n):
    # 如果昨天剩余的货物加上当天的货物先装尽量多
    cnt += (arr[i] + rest) // k 
    # 如果余下的货物大于arr[i],代表昨天剩余的货物还需要留一天
    # 这是不能接受的，剩余的货物必须今天运走
    if (arr[i] + rest) % k > arr[i]:
        cnt += 1
        rest = 0
    else:
        rest = (arr[i] + rest) % k
# 如果最后还有剩余的货物，那么需要再运一趟
if rest > 0:
    cnt += 1
print(cnt)

cpp

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 输入 n:货物数量, k:运输量
    int n, k;
    cin >> n >> k;

    // arr:货物重量
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // cnt:运输次数
    int cnt = 0;
    // rest:剩余的货物
    int rest = 0;

    for (int i = 0; i < n; i++) {
        // 如果昨天剩余的货物加上当天的货物先装尽量多
        cnt += (arr[i] + rest) / k;

        // 如果余下的货物大于 arr[i], 代表昨天剩余的货物还需要留一天
        // 这是不能接受的，剩余的货物必须今天运走
        if ((arr[i] + rest) % k > arr[i]) {
            cnt += 1;
            rest = 0;
        } else {
            rest = (arr[i] + rest) % k;
        }
    }

    // 如果最后还有剩余的货物，那么需要再运一趟
    if (rest > 0) {
        cnt += 1;
    }

    cout << cnt << endl; // 输出运输次数
    return 0;
}

java

import java.util.Scanner;

public class Delivery {

    public static void main(String[] args) {
        // 创建Scanner对象用于输入
        Scanner scanner = new Scanner(System.in);
        
        // 输入 n:货物数量, k:运输量
        int n = scanner.nextInt();
        int k = scanner.nextInt();

        // arr:货物重量
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }

        // cnt:运输次数
        int cnt = 0;
        // rest:剩余的货物
        int rest = 0;

        for (int i = 0; i < n; i++) {
            // 如果昨天剩余的货物加上当天的货物先装尽量多
            cnt += (arr[i] + rest) / k;

            // 如果余下的货物大于 arr[i], 代表昨天剩余的货物还需要留一天
            // 这是不能接受的，剩余的货物必须今天运走
            if ((arr[i] + rest) % k > arr[i]) {
                cnt += 1;
                rest = 0;
            } else {
                rest = (arr[i] + rest) % k;
            }
        }

        // 如果最后还有剩余的货物，那么需要再运一趟
        if (rest > 0) {
            cnt += 1;
        }

        // 输出运输次数
        System.out.println(cnt);
        
        // 关闭Scanner
        scanner.close();
    }
}