Bronze

Why Did the Cow Cross the Road

用一个数组记录前一次看到牛在那里即可。

没有看到过的牛,用\(-1\)标记。


Why Did the Cow Cross the Road II

直接\(O(n^2)\)枚举是否相交即可。

相交的特点是,另一组的两个端点分布在这组端点所切开圆的两半上。


Why Did the Cow Cross the Road III

按照到达的先后顺序排序。

显然一个牛到了,如果队列空了,他不让接水是没有意义的。

那就按照顺序一次接水,计算结束时间就好了。


Silver

Why Did the Cow Cross the Road

显然,我们要优先安排区间结束早的牛。

而对于一套牛,我们应该尽量选择离结束时间最近的鸡来带它。

因为比较靠前的鸡,可能后面还是有用处的。

这样的话,分别对两个排序,然后对于当前牛二分查找是否有符合要求的,贪心选鸡即可。


Why Did the Cow Cross the Road II

总共的灯数量不多。

我们用滑动窗口来解决。规定窗口大小为\(k\)。

每一移动只需要判断移出的一位和移入的一位是否损坏了即可。

不知道为什么数据范围这么小。


Why Did the Cow Cross the Road III

必须要通过道路相会的,一定是被隔离起来的两块区域。

准确的说,一定是要相会的两头奶牛分别属于不同的区域。

我们把所有马路存在的道路切断以后,把所有的联通块染成一样的颜色。

然后,枚举所有的奶牛对,判断他们是否属于同一个块就好了。


Gold

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注