【华为OD机试】真题A卷-连接器问题（C++）

一、题目描述

【华为OD机试】真题A卷-连接器问题（C++）

题目描述：

有一组区间[a0，b0]，[a1，b1]，…（a，b表示起点，终点），区间有可能重叠、相邻，重叠或相邻则可以合并为更大的区间；
给定一组连接器[x1，x2，x3，…]（x表示连接器的最大可连接长度，即x>=gap），可用于将分离的区间连接起来，但两个分离区间之间只能使用1个连接器；
请编程实现使用连接器后，最少的区间数结果。
区间数量<10000，a,b均 <=10000

连接器梳理<10000；x <= 10000

二、输入输出

输入描述：
区间组：[1,10],[15,20],[18,30],[33，40] 
连接器组：[5,4,3,2]
输出描述：
1
说明：
合并后：[1,10],[15,30],[33,40]，使用5, 3两个连接器连接后只剩下 [1, 40]。

三、参考示例

示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
输入：
[1,10],[15,20],[18,30],[33,40]
[5,4,3,2]
输出：
1
说明：
合并后：[1,10], [15,30], [33,40]，使用5, 3两个连接器连接后只剩下[1,40]。

四、解题思路

1. 编写splitString函数，将输入的字符串按逗号分隔转换为整数数组。
2. 定义自定义比较函数compareRanges，用于对区间进行排序。
3. 处理输入，读取并处理输入的ranges和connectors。
4. 对ranges进行排序，按照区间的起始值进行排序。
5. 合并重叠区间，计算区间之间的距离并排序。
6. 对connectors和区间距离进行排序。
7. 使用贪心算法，根据条件更新结果result。

五、参考代码

/*
 * @Author: mgc
 * @Date: 2024-02-02 17:47:00
 * @LastEditors: Do not edit
 * @LastEditTime: 2024-02-02 17:48:55
 */

// #include<set>
// #include<map>
// #include<list>
// #include<regex>
// #include<cmath>
// #include<queue>
// #include<stack>
// #include<bitset>
// #include<utility>
// #include<stdlib.h>
// #include<string.h>


#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

// 将输入字符串按逗号分隔转换为整数数组
vector<int> splitString(string inputStr) {
    vector<int> result;
    size_t pos = 0;
    while ((pos = inputStr.find(",")) != string::npos) {
        result.push_back(stoi(inputStr.substr(0, pos)));
        inputStr.erase(0, pos + 1);
    }
    result.push_back(stoi(inputStr));
    return result;
}

// 自定义比较函数，用于区间排序
bool compareRanges(vector<int>& a, vector<int>& b) {
    if (a[0] > b[0]) {
        return false;
    } else if (a[0] == b[0]) {
        if (a[1] > b[1]) {
            return false;
        }
    }
    return true;
}

int main() {
    // 输入处理
    string rangeStr, connectorStr;
    cin >> rangeStr;
    rangeStr.erase(remove(rangeStr.begin(), rangeStr.end(), '['), rangeStr.end());
    rangeStr.erase(remove(rangeStr.begin(), rangeStr.end(), ']'), rangeStr.end());
    vector<int> tempRanges = splitString(rangeStr);

    vector<vector<int>> ranges;
    for (int i = 0; i < tempRanges.size(); i++) {
        if (i % 2 != 0) {
            vector<int> singleRange;
            singleRange.push_back(tempRanges[i - 1]);
            singleRange.push_back(tempRanges[i]);
            ranges.push_back(singleRange);
        }
    }

    cin >> connectorStr;
    connectorStr.erase(remove(connectorStr.begin(), connectorStr.end(), '['),
                       connectorStr.end());
    connectorStr.erase(remove(connectorStr.begin(), connectorStr.end(), ']'),
                       connectorStr.end());
    vector<int> connectors = splitString(connectorStr);

    sort(ranges.begin(), ranges.end(), compareRanges);

    // 合并区间
    vector<vector<int>> mergedRanges;
    mergedRanges.push_back(ranges[0]);
    vector<int> rangeDiffs;
    for (int i = 1; i < ranges.size(); i++) {
        vector<int> range1 = mergedRanges[mergedRanges.size() - 1];
        vector<int> range2 = ranges[i];

        if (range2[0] <= range1[1]) {
            mergedRanges.pop_back();
            mergedRanges.push_back({range1[0], max(range1[1], range2[1])});
        } else {
            rangeDiffs.push_back(range2[0] - range1[1]);
            mergedRanges.push_back(range2);
        }
    }

    sort(rangeDiffs.begin(), rangeDiffs.end());
    sort(connectors.begin(), connectors.end());

    int result = mergedRanges.size();
    int idx = 0;
    for (int i = 0; i < connectors.size() && idx < rangeDiffs.size(); i++) {
        if (connectors[i] >= rangeDiffs[idx]) {
            idx++;
            result--;
        }
    }

    cout << result;

    return 0;
}

六、华为OD机试真题汇总目录

    【华为OD机试】真题汇总A+B+C+D券（Python实现）

    【华为OD机试】真题汇总A+B+C+D卷（JAVA实现）

    【华为OD机试】真题汇总A+B+C+D卷（C++实现）