有一个任务:
第一行包含两个整数 1≤n≤50000 和 1≤m≤50000——分别是线上的线段数和点数。接下来的 n 行包含两个整数 ai 和 bi (ai ≤ bi)——线段末端的坐标。最后一行包含 m 个整数——点的坐标。所有坐标不超过 10^8 模。如果一个点在它内部或在边界上,则它被认为属于一个线段。对于每个点,按照在输入中出现的顺序,输出它属于多少个段。
我想出了一个解决方案:从头开始对段进行排序。此外,我们在点和段上运行。我们看,如果该点属于段,那么我们增加计数器,并注意它至少属于一个段。接下来,我们看,如果该点不属于任何段,但属于至少一个段,那么它也不属于所有后续段。(因为这些段是按初始坐标的升序排列的)。但我对一项测试有疑问:
[6 6]
[2 3]
[2 5]
[3 5]
[2 7]
[5 7]
[3 7]
段,1 2 3 5 6 7 - 点。当答案是 0 3 5 5 3 3 时给出 0 3 5 5 1 1。我想知道我的算法中的错误在哪里。如果是的话,请把我推向正确的解决方案:)
导入 java.io.BufferedReader;导入 java.io.IOException;导入 java.io.InputStreamReader;导入 java.util.*;
import static java.lang.Integer.parseInt; /** * Created by Andrey on 31.12.2018. */ public class Stepic { static int scanInt() throws IOException { return parseInt(scanString()); } static String scanString() throws IOException { while (tok == null || !tok.hasMoreTokens()) { tok = new StringTokenizer(in.readLine()); } return tok.nextToken(); } static BufferedReader in; static StringTokenizer tok; public static void main(String[] args) throws IOException { in = new BufferedReader(new InputStreamReader(System.in)); int n = scanInt(); int m = scanInt(); int[] ans = new int[m]; List<Segment> segments = new ArrayList<>(); for(int i = 0 ; i < n; i++){ segments.add(new Segment(scanInt(),scanInt())); } segments.sort(Comparator.comparingInt(o -> o.x)); int[] dots = new int[m]; boolean[] dotsB = new boolean[m]; for(int i = 0; i < m; i++){ dots[i] = scanInt(); } for(int i = 0; i < dots.length; i++){ for (Segment segment : segments) { if (segment.x <= dots[i] && segment.y >= dots[i]) { ans[i]++; dotsB[i] = true; } else { if (dotsB[i]) { break; } } } } for(Segment segment : segments){ System.out.println(segment.x + " " + segment.y); } for (int an : ans) { System.out.print(an + " "); } } public static class Segment{ public int x; public int y; public Segment(int x, int y) { this.x = x; this.y = y; } } }
这不是真的。假设我们有 segment
[0 100] [10 20] [40 80]
。它们按原产地排序。该点50
属于第一段,不属于第二段。由此你得出一个奇怪的结论,“它也不属于所有后续的”。但是这是错误的。她属于[40 80]
。即使正确实施,您的方法也会非常低效,因为它会为每个点搜索整个段数组。对段数组进行排序的事实允许您根据条件检查提前结束搜索
segment.x > dots[i]
,但这并没有什么不同。平均而言,您必须检查每个点的一半。您正在尝试实现在线算法,即 一种独立于其他点处理每个点的算法。在任务下线的情况下明确告知你不需要这样做,即 所有测试点都是预先知道的。离线解决方案总是比在线解决方案更有效(或者,出于显而易见的原因,不会比它更差)。
如果任务是构建一个在线解决方案,那么一种有效的方法就是构建一个像线段树这样的经典数据结构。通过对细分进行排序,您实际上是朝着这个方向迈出了一步。但是,再一次,在您的问题陈述的框架内,为此付出努力是没有意义的。
该问题的有效离线解决方案可以基于合并两个排序数组的经典原理。两个数组——段和点——都必须提前排序,然后通过两个数组的同步传递,得到问题的答案。该算法的结构也类似于一维版本的扫描线算法(它支持许多“活动”段)。
例如,在 C++ 中
http://coliru.stacked-crooked.com/a/f37d52223571f42d
顺便说一句,您输入的正确答案
0 3 5 5 4 3
是,不是0 3 5 5 3 3
。删除所有与
dotsB[i]
. 逻辑错误的。