CCPC2019江西省赛-Problem G.Traffic

题目描述：

　　/*纯手打题面*/
　　Avin is observing the cars at a crossroads.He finds that there are n cars running in the east-west direction
with the i-th car passing the intersection at time a[i].There are another m cars running in the north-south
direction with the i-th car passing the intersection at time b[i].If two cars passing the intersections at 
the same time,a traffic crash occurs.In order to achieve world peace and harmony,all the cars running in the 
north-south direction wait the same time amount of integral time so that no two cars bump.You are asked the 
minimum waiting time.
/*纯手打题面*/

Input

n m
a[i]
b[i]
(1<=n,m<=1000;1<=ai,bi<=1000)

Output

The minimum waiting time(integer).

题解心得：

啊啊啊啊啊啊啊啊啊啊啊啊，当时在比赛的时候翻了好久词典，终于把这个题目的意思大概搞懂了

然后和我们队的大佬讨论了好久

一开始爆搜O(N³)

然后想了好久奇奇怪怪的方法，分治什么的，然后就剪枝优化。

但是最后用标记法把时间复杂度压到了O(N²)。

大致思路：

枚举时间（一个循环）

在每个循环里标记a[i]所占的时间点（布尔数组c）

同时标记b[i]+t的时间点（布尔数组d）

接着c&&d;

就可以了。

这题真的水，不加剪枝也能AC。

代码：

以后附。

原文链接:https://www.cnblogs.com/XYYXP/p/JXCPC_2019_Problem_G.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有