codeforces #319 div 2 E C. Points on Plane (分块)

初识分快.

引一段题解:

Let’s split rectangle 106 × 106 by vertical lines into 1000 rectangles 103 × 106. Let’s number them from left to right. We’re going to pass through points rectangle by rectangle. Inside the rectangle we’re going to pass the points in increasing order of y-coordinate if the number of rectangle is even and in decreasing if it’s odd.

Let’s calculate the maximum length of such a way. The coordinates are independent. By y-coordinate we’re passing 1000 rectangles from0 to 106, 109 in total. By x-coordinate we’re spending 1000 to get to the next point of current rectangle and 2000 to get to next rectangle. That means, 2 * 109 + 2000000 in total, which perfectly fits.

The complexity is O(n * log(n))

 并不会做,看了题解写的,感觉好神奇…

然后加深了sort的cmp函数的理解...

原来还可以这么写.

有点开心,因为觉得解法有点美.

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz