0

任务。给定一组段 {[0, 0], [1, 1], . . . , [−1, −1]} 与直线上的整数坐标，找到最小点数，使得每个线段至少包含一个点。也就是说，找到一组最小大小的整数，使得对于任何段 [, ] 都有一个点 ∈ 使得 ≤ ≤ 。

输入格式。输入的第一行包含段数。以下每一行都包含两个整数，并且（由空格分隔）定义第 -th 段的端点坐标。

约束。1≤≤100；0 ≤ ≤ ≤ 109 对于所有 0 ≤ < 。

输出格式。输出第一行上的最小点数和第二行上点的整数坐标（用空格分隔）。您可以按任何顺序输出点。如果有很多这样的点集，则可以输出任何集。（不难看出，总是存在一组最小尺寸的点，使得所有点的坐标都是整数。）

我已经针对这个问题实施了一个解决方案，并尝试对其进行压力测试。它真的很好用。但是在将其提交到 coursera 时，我收到“未知信号 11” 有人可以帮我解决这个问题吗？

#include <algorithm>
#include <iostream>
#include <climits>
#include <vector>

using std::vector;

struct Segment 
{
  int start, end;
};
bool compareByStart(const Segment &a, const Segment &b)
{
    return a.start < b.start;
}
vector<int> optimal_points(vector<Segment> &segments) 
{
  vector<int> points;
  sort(segments.begin(), segments.end(), compareByStart);
  for (long i = 0; i < segments.size(); ++i) 
  {
    int temp=i;
    int min=segments[i].end;
    while(segments[i].start<=segments[temp].end && i<segments.size())
    {
        if(segments[i].end<min)
        {
            min=segments[i].end;
        }
        i++;
    }
    points.push_back(min);
    i=temp;
    while(segments[i+1].start<=min)
    {
        i++;
    }
  }
  return points;
}

int main() {
  int n;
  std::cin >> n;
  vector<Segment> segments(n);
  for (size_t i = 0; i < segments.size(); ++i) {
    std::cin >> segments[i].start >> segments[i].end;
  }
  vector<int> points = optimal_points(segments);
  std::cout << points.size() << "\n";
  for (size_t i = 0; i < points.size(); ++i) {
    std::cout << points[i] << " ";
  }
}
4

1 回答 1

1

这是错误的：

while(segments[i].start<=segments[temp].end && i<segments.size())

您应该在使用它访问元素之前检查索引，而不是之后：

while(i < semgents.size() && segments[i].start<=segments[temp].end)

后来你有一个看起来有点吓人的循环，因为你根本不检查索引：

while(segments[i+1].start<=min)
{
    i++;
}

这也可以轻松访问segments越界。

于 2020-07-08T14:36:52.417 回答