主页 / user-579843

GrosMan's questions

Martin Hope
GrosMan
Asked: 2024-01-09 07:49:50 +0000 UTC
  • 10

有一个关于用线段覆盖点的经典问题 - 数轴上有 n 个整数点，该问题要求找到能够覆盖所有点的指定长度的线段的最小数量。如果一个点位于线段的边界上，则该点被视为被覆盖。例如，我们有五个坐标为 {1, 2, 3, 4, 5} 的点和单位长度的线段 - 对于这样一个集合，问题的答案将为 3，因为所有点都可以被 3 个线段覆盖 [ 1,2]、[3,4]、[4,5]，这在两个段中不起作用。这个问题可以通过贪心算法轻松解决。

int Cover(std::vector<int>& data, int l) {
//сортируем вектор координат точек
    std::sort(data.begin(), data.end());
    

    int interval_count = 1; // количество отрезков
    int r_point = data[0] + l; //правая граница последнего установленного отрезка
    for(int& elem : data){
        if(elem > r_point){
            interval_count += 1;
            r_point = elem + l;
        }
    }
    
    return interval_count;
}

所以我对逆问题感兴趣——根据条件，给定一组点和线段数量，找到线段的最小长度。事实上，我没有想出比尝试不同长度更好的方法:(我基于对 (0, data.back() - data.front()) 范围内的长度的二进制搜索构建了我的解决方案。检查搜索中的每个长度 - 它们将覆盖或 k 个长度为 l 的段（按条件），一组数据点（经典问题的修改解决方案）。

bool CanCover(const std::vector<int>& data, int l, int k){
    
    --k;
    int r_point = data[0] + l;
    
    for(const int& elem : data){
        if(elem > r_point){
            --k;
            r_point = elem + l;
            if (k < 0) return false;
        }
    }
    
    return true;
}

这是二分搜索本身

int Binary(std::vector<int>& data, int k){
    if(k >= data.size()) return 0; //если отрезков больше чем точек, то отрезки могут быть длиной 0 и лежать на каждой из точек
    
    std::sort(data.begin(), data.end());
    
    //границы поиска
    int left = 0;
    int right = data.back() - data.front();
    
    while(left < right){
            int mid = (left + right) / 2;
            
            if(CanCover(data, mid, k)) right = mid;
            else left = mid + 1;
    }
    
    return left;
}

但测试结果表明，二分查找的解决方案速度不够快。有没有一种方法可以在不遍历所有长度的情况下找到线段的最小长度？像贪婪算法之类的东西，就像经典问题一样？

c++