[已解决]求大神帮忙设计一个算法！！！

xxlxxl

我有一个array A，长度为n，其中每一个元素代表一个传感器同时表示了自己在这条横线上的位置，比如A[0]等于1，A[1]等于4，那这两个传感器之间相距3。如果两个传感器间距离为 r 就可以接收到对方的电波。
现在需要设计一个算法返回array中所有可以互相接收电波的传感器的索引。
有个例子：

A : [1, 4, 5, 8, 9, 10, 12], r = 2: return {{1, 2}, {3, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}, {5, 6}}.
其中 A[3] 可以接收到 A[6] 的信号是因为 A[5] 可以接收到 A[6] 的信号，同时 A[3] 可以接收到 A[5] 的信号。

最佳答案

月排行榜 / 总排行榜

wp231957

2021-3-20 07:49:11

再多给几组测试案例，

跳转到最佳答案楼层

wp231957

再多给几组测试案例，

人造人

#include <iostream>
#include <vector>
#include <utility>

const std::vector<std::pair<size_t, size_t>> get(const std::vector<size_t> &v, size_t r) {
    std::vector<std::pair<size_t, size_t>> result;
    for(size_t i = 0; i < v.size(); ++i) {
        size_t prev = v[i];
        for(size_t j = i + 1; j < v.size(); ++j) {
            if(prev + r >= v[j]) {
                prev = v[j];
                result.push_back(std::pair<size_t, size_t>(i, j));
            } else break;
        }
    }
    return result;
}

std::ostream &operator<<(std::ostream &os, const std::vector<std::pair<size_t, size_t>> &rhs) {
    for(const auto &i: rhs) {
        os << "{" << i.first << ", " << i.second << "}" << std::endl;
    }
    return os;
}

int main() {
    std::vector<size_t> v = {1, 4, 5, 8, 9, 10, 12};
    size_t r = 2;
    std::vector<std::pair<size_t, size_t>> result = get(v, r);
    std::cout << result << std::endl;
    return 0;
}