覆盖较大线的最小线段数 [英] Minimum number of line segments to cover a bigger line
问题描述
我给出了相同长度的 n 线段(1维)的坐标,我需要找到这些线段的最小数量以完全覆盖更大的线或找出这是不可能的。
I am given the coordinates of n line segments (1-dimensional) of same length, and I need to find the minimal number of these line segments to fully cover the bigger line or find out that this is impossible.
较大的行从 0 开始,以 L 结束。线段可以从 [0-D,LD] 范围开始,并且所有线段都具有相同的长度 2 * D 。
The bigger line starts from 0 and ends at L. The line segments can start from the range [0-D, L-D] and all have the same length 2*D.
因此,例如对于以下输入:
So, for example for the following input:
15 2 4 // L, n, D
-2 7 // beginning coordinates of line segments
21 14 4
10 4 6 3 16 17 -1 2 14 11 12 8 5 1
9 9 3
-2 -1 4 0 5 -3 6 3 1
14 12 5
-3 -2 7 5 3 -4 2 -5 0 8 9 6
有以下输出:
Case #1: impossible
Case #2: 3
Case #3: 2
Case #4: 2
为了解决这个问题,我使用贪心算法并选择线段,以便它们之间的交叉点最小。这是我的java代码:
In order to solve this problem I use the greedy algorithm and choose line segments, so that the intersections between them are minimal. Here's my java code:
// read L, n, D
// read line segments to segments[] array
segments[n] = Integer.MAX_VALUE;
Arrays.sort(segments);
int current = -1;
for (int i = n-1; i >= 0; i--)
if (segments[i] <= 0) {
current = i;
break;
}
if (current == -1) {
System.out.println("Case #" + k + ": impossible");
continue;
}
int count = 1;
boolean poss = true;
for (int i = 0; i < L - 2* D;) {
count++;
int next = getNextSegment(current);
if (next == current) {
poss = false;
break;
}
current = next;
i = segments[current];
}
if (!poss)
System.out.println("Case #" + k + ": impossible");
else
System.out.println("Case #" + k + ": " + count);
这是我的帮助方法获得下一个线段:
And here is my helper method that gets the next line segment:
int getNextSegment(int current) {
int i = current;
while (segments[i] <= segments[current] + 2* D)
i++;
return i-1;
}
我的算法正确生成上述输出,但我的代码中仍有一些错误我无法找到我的程序失败的测试用例。您认为应该修复什么?
My algorithms produces the aforementioned output correctly, but there's still some bug in my code and I wasn't be able to find the test case, where my program fails. What do you think should be fixed?
推荐答案
我设法编辑您的解决方案,为列出的所有数据集生成正确的输出提供的链接。我的编辑如下:
I managed to edit your solution to generate the correct output for all data sets listed on the provided link. My edits are as follows:
- 更改
段
数组大小n + 1
大小n
,删除末尾的Integer.MAX_VALUE条目。 - 将
segments [i]< = 0
更改为segments [i] -D< = 0
是没有条目< = 0,但是有一个条目与0相交。 - 从
更改for循环标题for(int i = 0; i< L - 2 * D;)
到for(int i = 0; i< L - D;)
- 在
getNextSegment
方法中添加了边界检查。
- Changed
segments
array from sizen+1
to sizen
, removing the Integer.MAX_VALUE entry at the end. - Changed
segments[i] <= 0
tosegments[i]-D <= 0
for cases where there is no entry <= 0, but there is an entry that intersects 0. - Changed the for loop header from
for (int i = 0; i < L - 2 * D;)
tofor (int i = 0; i < L - D;)
- Added a boundary check in the
getNextSegment
method.
For引用,我得到的代码如下:
For reference, my resulting code is as follows:
Arrays.sort(segments);
int current = -1;
for (int i = n-1; i >= 0; i--) {
if (segments[i]-D <= 0) {
current = i;
break;
}
}
if (current == -1) {
System.out.println("Case #" + k + ": impossible");
continue;
}
int count = 1;
boolean poss = true;
for (int i = segments[current]; i < L-D;) {
count++;
int next = getNextSegment(current);
if (next == current) {
poss = false;
break;
}
current = next;
i = segments[current];
}
if (!poss)
System.out.println("Case #" + k + ": impossible");
else
System.out.println("Case #" + k + ": " + count);
使用编辑后的 getNextSegment
方法:
int getNextSegment(int current) {
int i = current;
while(i < segments.length && segments[i] <= segments[current] + 2 * D)
i++;
return i - 1;
}
这篇关于覆盖较大线的最小线段数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!