当前位置：首页 > article >正文

机试题——维修工

article 2024/12/23 9:41:04

题目描述

维修工要给n个客户更换设备，为每个用户更换一个设备。维修工背包内最多装k个设备，如果背包里有设备可以直接前往下一个客户更换或回公司补充设备，没有则需要回公司取设备。这些客户有优先级，维修工需要按照优先级给客户更换设备，优先级level用数字表示，数字小的优先级高。维修工从公司出发，给n个客户更换设备，最后再返回公司。请计算维修工完成这项工作所需要经历的最短总距离是多少。维修工可以走斜线。

输入描述

第一行两个正整数 n, k(1 ≤ k ≤ n ≤ 2000)，表示客户数和维修工背包容量。
第二行两个正整数 x, y ，用空格分隔(1 ≤ x, y ≤ 10^6)，表示公司的坐标。
接下来 n 行每行三个正整数 x_i, y_i, level_i，用空格分隔，表示第 i 个客户的位置坐标 (x_i, y_i) 和优先级 level_i。
保证所有客户优先级不同，客户和公司坐标不会重叠。

输出描述

输出最短总距离，结果四舍五入并保留一位小数，例如: 9.0。

用例输入

输出

9.2

从 (1, 1) → (3, 1) → (1, 1) → (1, 2) → (3, 2) → (1, 1)
计算距离：

(1, 1) → (3, 1) = 2
(3, 1) → (1, 1) = 2
(1, 1) → (1, 2) = 1
(1, 2) → (3, 2) = √5 ≈ 2.236

总距离：2 + 2 + 1 + √5 = 9.236，四舍五入后为 9.2。

解题思路

题目要求按照客户的优先级来安排维修顺序。因为客户优先级是通过数字表示的，数字越小优先级越高。首先需要根据 level 对客户进行排序。

如果背包里有修理工具，则有两种情况：

情况1：直接去下一个地方修理
情况2：先去公司补工具，再去修理

如果背包里没有工具，只能回公司补工具，再修理。（同情况2）

使用 记忆化搜索 来避免重复计算。使用 memo[i][j] 来表示“维修完第 i 个客户，并且背包中剩余 j 个设备时，维修工完成任务所需的最短距离。

代码

对于每一个客户 i，有两种选择：

直接前往下一个客户（如果背包中有足够的设备，即 j > 0）：从客户 i 前往客户 i+1，消耗的距离为 dis(data[i].x, data[i].y, data[i+1].x, data[i+1].y)。更新状态为 memo[i+1][j-1]。
返回公司补充设备：从客户 i 返回公司，消耗的距离为 dis(data[i].x, data[i].y, cx, cy)。从公司再次前往客户 i+1，消耗的距离为 dis(data[i+1].x, data[i+1].y, cx, cy)。更新状态为 memo[i+1][k-1]（因为补充了设备，背包重新装满，然后又消耗了1个）。

需要取这两种选择的最小值。

当处理到最后一个客户（i == n-1）时，只需要从客户返回公司，消耗的距离为 dis(data[i].x, data[i].y, cx, cy)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<map>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<set>
using namespace std;

double dis(int x1, int y1, int x2, int y2) {
    // 计算两点间的欧几里得距离
    return (double)sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

struct customer {
    int x, y, level;  // 客户的坐标和优先级
    bool operator < (const customer& other) const {
        return level < other.level;  // 按照优先级排序
    }
};

double memo[2001][2001] = { 0 };
int n, k;  // n: 客户数, k: 背包容量
int cx, cy; // 公司坐标

// 已经完成前i个顾客，背包里还有j个工具时最小距离
double dfs(vector<customer>& data, int i, int j) {
    if (memo[i][j] > 0) return memo[i][j];
    // 计算到公司距离
    double cur = dis(data[i].x, data[i].y, cx, cy);
    double& res = memo[i][j];
    res = INT32_MAX;
    if (i < n - 1) { // 非最后一个客户
        // 回公司补充装备，再去下一个地方维修 
        res = min(res, dfs(data, i + 1, k - 1) + cur + dis(data[i + 1].x, data[i + 1].y, cx, cy));
        if (j > 0) {
            // 有剩余工具 直接去维修
            res = min(res, dfs(data, i + 1, j - 1) + dis(data[i].x, data[i].y, data[i + 1].x, data[i + 1].y));
        }
    }
    // i为 n-1
    else {
        res = cur;
    }
    cout << i << "  " << j << "  " << res << endl;
    return res;
}

int main()
{
    ios::sync_with_stdio(false);  // 关闭与 C 的同步
    cin.tie(nullptr);             // 解除 cin 与 cout 的绑定

    cin >> n >> k >> cx >> cy;
    vector<customer> data(n);
    for (int i = 0; i < n; i++) {
        cin >> data[i].x >> data[i].y >> data[i].level;
    }
    sort(data.begin(), data.end());
    cout << dfs(data, 0, k - 1)+dis(data[0].x, data[0].y,cx,cy) << endl;
}