题面简述

题目给定了一个机房的布局，其中有多个机柜，每个机柜有一定数量的服务器需求，并且所有的机柜都排成一条直线。我们需要计算将所有服务器从原点搬运到机柜所需的最小距离。每次搬运时，小明可以携带最多 k 台服务器，并且每次搬运完后需要返回原点。

解题思路

1. 输入和输出说明：

   • 输入：有 n 个机柜，每个机柜有一个位置（可能为正数或负数），每个机柜需要一定数量的服务器。
   • 输出：计算最小的搬运总距离。

2. 问题分析：

   • 我们要考虑搬运服务器的顺序及搬运的方式。对于每个机柜，小明每次最多可以搬运 k 台服务器，搬运过程需要根据机柜的位置来决定搬运的顺序，尽量让每次搬运的距离最短。
   • 小明每次需要返回原点，因此如果搬运的机柜很远，距离将会显著增加。
   • 我们需要将正数位置和负数位置的机柜分开处理，分别计算它们的搬运距离。

3. 算法设计：

   • 正负位置分离：我们可以把机柜的位置分成正数和负数两类，分别进行处理。
   • 排序：机柜按照距离从大到小排序。
   • 搬运策略：每次从原点出发，尽可能多地搬运 k 台服务器，先搬运到距离原点近的机柜，然后返回原点。

4. 计算总距离：

   • 对每个机柜，计算需要多少次搬运，然后每次搬运都会增加两倍的该机柜的距离（因为需要来回），总距离为所有搬运距离的总和。因为最后可以不回原点，所以最后要减去最大的距离。

5. 复杂度分析：

   • 对于每个机柜，我们需要对其位置进行排序。排序的时间复杂度是 O(n log n)。
   • 模拟搬运服务器，时间复杂度是 O(n max(m))

代码实现

Python

def min_transport_distance(n, k, positions, demands):
    total_distance = 0
    
    # 分别处理正数和负数位置的机柜
    positive_cabinets = []
    negative_cabinets = []
    
    # 将机柜分为两类，正数位置和负数位置
    for i in range(n):
        if positions[i] >= 0:
            positive_cabinets.append([positions[i], demands[i]])
        else:
            negative_cabinets.append([-positions[i], demands[i]])
    
    # 先搬运距离最远的机柜，正数位置按距离排序jin
    positive_cabinets.sort(key=lambda x: x[0])
    negative_cabinets.sort(key=lambda x: x[0])

    # 处理正数位置的机柜
    max_distance = 0
    while len(positive_cabinets) > 0:
        kk = k
        dis = positive_cabinets[-1][0]
        max_distance = max(max_distance, dis)
        total_distance += dis * 2
        while kk > 0 and len(positive_cabinets) > 0:
            num = min(kk, positive_cabinets[-1][1])
            kk -= num
            positive_cabinets[-1][1] -= num
            if positive_cabinets[-1][1] == 0:
                positive_cabinets.pop()
    # 处理负数位置的机柜
    while len(negative_cabinets) > 0:
        kk = k
        dis = negative_cabinets[-1][0]
        max_distance = max(max_distance, dis)
        total_distance += dis * 2
        while kk > 0 and len(negative_cabinets) > 0:
            num = min(kk, negative_cabinets[-1][1])
            kk -= num
            negative_cabinets[-1][1] -= num
            if negative_cabinets[-1][1] == 0:
                negative_cabinets.pop()

    # 扣除最远的机柜的搬运距离，因为它在两次搬运中被计算了一次
    total_distance -= max_distance
    return total_distance

# 输入读取
n, k = map(int, input().split())  # n 为机柜数量，k 为每次搬运的最大服务器数量
positions = list(map(int, input().split()))  # 每个机柜的位置
demands = list(map(int, input().split()))  # 每个机柜需要的服务器数量

# 输出最小距离
print(min_transport_distance(n, k, positions, demands))

Java

import java.util.*;

public class Main {
    
    public static int minTransportDistance(int n, int k, int[] positions, int[] demands) {
        int totalDistance = 0;

        // 分别处理正数和负数位置的机柜
        List<int[]> positiveCabinets = new ArrayList<>();
        List<int[]> negativeCabinets = new ArrayList<>();

        // 将机柜分为两类，正数位置和负数位置
        for (int i = 0; i < n; i++) {
            if (positions[i] >= 0) {
                positiveCabinets.add(new int[]{positions[i], demands[i]});
            } else {
                negativeCabinets.add(new int[]{-positions[i], demands[i]});
            }
        }

        // 先搬运距离最远的机柜，正数位置按距离排序
        positiveCabinets.sort((a, b) -> Integer.compare(a[0], b[0]));
        negativeCabinets.sort((a, b) -> Integer.compare(a[0], b[0]));

        // 处理正数位置的机柜
        int maxDistance = 0;
        while (positiveCabinets.size() > 0) {
            int kk = k;
            int dis = positiveCabinets.get(positiveCabinets.size() - 1)[0];
            maxDistance = Math.max(maxDistance, dis);
            totalDistance += dis * 2;
            
            while (kk > 0 && positiveCabinets.size() > 0) {
                int num = Math.min(kk, positiveCabinets.get(positiveCabinets.size() - 1)[1]);
                kk -= num;
                positiveCabinets.get(positiveCabinets.size() - 1)[1] -= num;
                
                if (positiveCabinets.get(positiveCabinets.size() - 1)[1] == 0) {
                    positiveCabinets.remove(positiveCabinets.size() - 1);
                }
            }
        }

        // 处理负数位置的机柜
        while (negativeCabinets.size() > 0) {
            int kk = k;
            int dis = negativeCabinets.get(negativeCabinets.size() - 1)[0];
            maxDistance = Math.max(maxDistance, dis);
            totalDistance += dis * 2;
            
            while (kk > 0 && negativeCabinets.size() > 0) {
                int num = Math.min(kk, negativeCabinets.get(negativeCabinets.size() - 1)[1]);
                kk -= num;
                negativeCabinets.get(negativeCabinets.size() - 1)[1] -= num;
                
                if (negativeCabinets.get(negativeCabinets.size() - 1)[1] == 0) {
                    negativeCabinets.remove(negativeCabinets.size() - 1);
                }
            }
        }

        // 扣除最远的机柜的搬运距离，因为它在两次搬运中被计算了一次
        totalDistance -= maxDistance;

        return totalDistance;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 输入读取
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        
        int[] positions = new int[n];
        int[] demands = new int[n];
        
        for (int i = 0; i < n; i++) {
            positions[i] = scanner.nextInt();
        }
        
        for (int i = 0; i < n; i++) {
            demands[i] = scanner.nextInt();
        }
        
        // 输出最小距离
        System.out.println(minTransportDistance(n, k, positions, demands));
        
        scanner.close();
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int minTransportDistance(int n, int k, vector<int>& positions, vector<int>& demands) {
    int totalDistance = 0;
    vector<pair<int, int>> positiveCabinets;
    vector<pair<int, int>> negativeCabinets;

    // 将机柜分为两类，正数位置和负数位置
    for (int i = 0; i < n; i++) {
        if (positions[i] >= 0) {
            positiveCabinets.push_back({positions[i], demands[i]});
        } else {
            negativeCabinets.push_back({-positions[i], demands[i]});
        }
    }

    // 先搬运距离最远的机柜，正数位置按距离排序
    sort(positiveCabinets.begin(), positiveCabinets.end());
    sort(negativeCabinets.begin(), negativeCabinets.end());

    // 处理正数位置的机柜
    int maxDistance = 0;
    while (!positiveCabinets.empty()) {
        int kk = k;
        int dis = positiveCabinets.back().first;
        maxDistance = max(maxDistance, dis);
        totalDistance += dis * 2;

        while (kk > 0 && !positiveCabinets.empty()) {
            int num = min(kk, positiveCabinets.back().second);
            kk -= num;
            positiveCabinets.back().second -= num;
            if (positiveCabinets.back().second == 0) {
                positiveCabinets.pop_back();
            }
        }
    }

    // 处理负数位置的机柜
    while (!negativeCabinets.empty()) {
        int kk = k;
        int dis = negativeCabinets.back().first;
        maxDistance = max(maxDistance, dis);
        totalDistance += dis * 2;

        while (kk > 0 && !negativeCabinets.empty()) {
            int num = min(kk, negativeCabinets.back().second);
            kk -= num;
            negativeCabinets.back().second -= num;
            if (negativeCabinets.back().second == 0) {
                negativeCabinets.pop_back();
            }
        }
    }

    // 扣除最远的机柜的搬运距离，因为它在两次搬运中被计算了一次
    totalDistance -= maxDistance;

    return totalDistance;
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> positions(n);
    vector<int> demands(n);

    for (int i = 0; i < n; i++) {
        cin >> positions[i];
    }

    for (int i = 0; i < n; i++) {
        cin >> demands[i];
    }

    // 输出最小距离
    cout << minTransportDistance(n, k, positions, demands) << endl;

    return 0;
}

题目内容

机房中共有$n$个机柜位于一条直线上，第$i$个机柜的位置用坐标$x_i$表示，$0≤i≤n-1$.

现有一批服务器需搬运到$n$个机柜处,第$i$个机柜需要$m_i$台服务器。

小明负责搬运工作，小明和所有服务器最初都位于原点$0$，小明一次最多可以搬运$k$台服务器。小明必须从原点提取所需数量的服务器，将它们搬运到各自的机柜，然后返回原点提取下一批服务器。

请计算将所有服务器搬运到机柜所需的最小距离。搬运完所有服务器后，

小明无需返回原点。

输入描述

第一行包含两个整数$n$和$k$，$1≤n≤10^5,1≤k≤10^5$

第二行包含$n$个整数，表示$n$个机柜的坐标 $x_0， x_1 ,... x_{n-1},-10^9≤x≤10^9$

第三行包含$n$的整数，表示$n$个机柜所需的服务器数量$m_0，m_1，… m_{n-1},1≤m_i≤10$

输出描述

将所有服务器搬运到机柜所需的最小距离。

样例1

输入

4 1
1 3 2 4
1 1 1 1

输出

16

说明

小明每次只能搬$1$台服务器，因为每次搬运都需要返回原点，小明的最短搬运路径为$0→1→0→2→0→3→0→4$，将每段路径相加得到 $1+1+2+2+3+3+4=16$

样例2

输入

5 3
-5 -10 -7 6 8
1 1 1 1 2

输出

26

说明

小明每次可以搬$3$台服务器，最短搬运路径为$0→6→8→0→(-5)→(-7) →(-10)$，将每段路径相加得到$6+2+8+5+2+3=26$