清华OJ灯塔

灯塔

• • 题目
  • 分析
  • 我的代码：

题目

Description
As shown in the following figure, If another lighthouse is in gray area, they can beacon each other.

For example, in following figure, (B, R) is a pair of lighthouse which can beacon each other, while (B, G), (R, G) are NOT.

Input
1st line: N
2nd ~ (N + 1)th line: each line is X Y, means a lighthouse is on the point (X, Y).
Output
How many pairs of lighthourses can beacon each other
( For every lighthouses, X coordinates won’t be the same , Y coordinates won’t be the same )
Example
Input
3
2 2
4 3
5 1
Output
1
Restrictions
For 90% test cases: 1 <= n <= 3 * 105
For 95% test cases: 1 <= n <= 106
For all test cases: 1 <= n <= 4 * 106
For every lighthouses, X coordinates won’t be the same , Y coordinates won’t be the same.
1 <= x, y <= 10^8
Time: 2 sec
Memory: 256 MB
Hints
The range of int is usually [-231, 231 - 1], it may be too small.
描述
海上有许多灯塔，为过路船只照明。

（图一）
如图一所示，每个灯塔都配有一盏探照灯，照亮其东北、西南两个对顶的直角区域。探照灯的功率之大，足以覆盖任何距离。灯塔本身是如此之小，可以假定它们不会彼此遮挡。

（图二）
若灯塔A、B均在对方的照亮范围内，则称它们能够照亮彼此。比如在图二的实例中，蓝、红灯塔可照亮彼此，蓝、绿灯塔则不是，红、绿灯塔也不是。
现在，对于任何一组给定的灯塔，请计算出其中有多少对灯塔能够照亮彼此。
输入
共n+1行。
第1行为1个整数n，表示灯塔的总数。
第2到n+1行每行包含2个整数x, y，分别表示各灯塔的横、纵坐标。
输出
1个整数，表示可照亮彼此的灯塔对的数量。
样例
见英文题面
限制
对于90%的测例：1 ≤ n ≤ 3×105
对于95%的测例：1 ≤ n ≤ 106
全部测例：1 ≤ n ≤ 4×106
灯塔的坐标x, y是整数，且不同灯塔的x, y坐标均互异
1 ≤ x, y ≤ 10^8
时间：2 sec
内存：256 MB
提示
注意机器中整型变量的范围，C/C++中的int类型通常被编译成32位整数，其范围为[-231, 231 - 1]，不一定足够容纳本题的输出。

分析

A和B能够相互照亮的条件（假设A(x) 而问题的关键就在于在这样的数据规模下如何快速的统计出“顺序对”的个数。 如果只是单纯的O(n^2)的算法显然是效率不够的。 那，如何从向量中快速的统计出“顺序对”的个数？ 这里大概思考之后可以联想到 归并排序。
归并排序的关键也就是用分治的策略，将原问题一分为二的递归下去，最后的关键步骤只是将左右两个有序的区间合并起来即可。 而很快会发现，在合并的过程中似乎我们就可以顺便统计“顺序对”的个数。
考虑这样的一种情形： 目前左右两个有序区间，分别有指针 i, j 指向该区间下一个要合并的元素。 当a[i] < a[j]的时候（不可能相等，原题目已经说明），此时 a[i] 就要被合并。 而 a[j]以及所有右区间大于 a[j] 的元素 其实都与 a[i] 构成“顺序对”。 统计完后，i 指向 i++的元素，且区间也都是没有重叠部分的，所以也并不会重复计数。 这样在归并排序合并的同时，也将所有的“顺序对”无重复无遗漏地记录了下来。
算法复杂度也就是O(nlogn)的。

我的代码：

#include 
#define MAXN 4000010
//如果是中国石油大学的同学，请不要抄袭，不然0分处理时很尴尬，请独立完成，有不理解的地方可与我交流
struct Point 
{long x;long y;
}points[MAXN];long count;
long src[MAXN];
long des[MAXN];void qsort(Point ps[], int l, int r)
{if (l < r){int i = l, j = r;Point tmp;tmp.x = ps[i].x;tmp.y = ps[i].y;int key = ps[i].x;while (i < j){while (i < j && key < ps[j].x) --j;ps[i].x = ps[j].x;ps[i].y = ps[j].y;while (i < j && ps[i].x < key) ++i;ps[j].x = ps[i].x;ps[j].y = ps[i].y;}ps[i].x = tmp.x;ps[i].y = tmp.y;qsort(ps, l, i - 1);qsort(ps, i + 1, r);}
}void merge(long *src, long *des, int start, int mid, int end)
{int i = start, j = mid + 1;int k = start;while (i != mid + 1 && j != end + 1){if (src[i] < src[j]){des[k++] = src[i++];count += end - j + 1;}else des[k++] = src[j++];}while (i != mid + 1) des[k++] = src[i++];while (j != end + 1) des[k++] = src[j++];for (i = start; i != end + 1; ++i)src[i] = des[i];
}
void mergeSort(long *src, long *des, int start, int end)
{int mid;if (start < end){mid = (start + end) >> 1;mergeSort(src, des, start, mid);mergeSort(src, des, mid + 1, end);merge(src, des, start, mid, end);}
}int main()
{int n;int i;scanf("%d", &n);for (i = 0; i < n; ++i)scanf("%ld %ld", &points[i].x, &points[i].y);qsort(points, 0, n - 1);for (i = 0; i < n; ++i)src[i] = points[i].y;count = 0;mergeSort(src, des, 0, n - 1);printf("%ld\n", count);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！