c - 提高效率 "lighthouse"

Question

问题描述:

海中有许多灯塔。海的范围是[1, 10^7] × [1, 10^7]。

每个灯塔都可以照亮西南和东北地区。光的力量足以覆盖任何距离。

如果灯塔A和B都在照亮区，说明它们可以互相照亮。

输入有 n+1 行:第一行是灯塔的数量。第二行到第n行分别是灯塔的横纵坐标。

输出只有一行:一对可以互相照亮的灯塔。

例如:

输入:

3
2 2
4 3
5 1

输出:

1

注意:

灯塔的坐标是int。所有灯塔的横纵坐标都不一样。

1 ≤ x, y ≤ 10^7

我的代码效率很低。请帮我修改我的代码。非常感谢!

这是我的代码。

    #include<stdlib.h>
    int main()
    {
        int n,i,j,s;
        int *x,*y;
        scanf("%d",&n);
        x=(int *)malloc(n*sizeof(int));
        y=(int *)malloc(n*sizeof(int));
        for(i=0;i<n;i++)
        {
           scanf("%d %d",&x[i],&y[i]);
        }
        s=0;
        for(i=0;i<n-1;i++)
        for(j=i+1;j<n;j++)
        {
        if((x[i]>x[j]&&y[i]>y[j])||(x[i]<x[j]&&y[i]<y[j]))
            s++;
        }
        printf("%d\n",s);
        free(x);
        free(y);
        return 0;
        }

Answer 1

我没有足够的声望直接发表评论，所以我会详细并在这里留下答案。

您的算法使用嵌套循环进行配对计算并具有 O(n²) 时间复杂度，这就是您的算法对于大输入速度慢的原因(大在这里并不意味着坐标值，但灯塔的数量)。首先让我们看看我们可以用一个示例输入来优化什么:

3
1 1 (P_a)
2 2 (P_b)
3 3 (P_{c )}

使用您的算法，执行逻辑将是:

1. 计数=0
2. P_a 和 P_b 是一对？没错，数++
3. P_a 和 P_c 是一对？没错，数++
4. P_b 和 P_c 是一对？没错，数++
5. 输出计数

实际上存在可以消除的冗余计算:

确定新添加的灯塔是否可以被现有灯塔照亮。

注意P_a的NE区域实际上包含P_b的NE区域，所以如果一个新的灯塔落入P_b 的 NE 区域，这隐含地意味着它被 P_a 和 P_b 照亮。所以如果我们在海中有 P_a 和 P_b 并添加 P_c，我们实际上不需要用 P< 计算两次sub>a 和 P_b 分开。

假设我们有以下记录，其中记录了灯塔的照明交叉区域:
一个。计数=0； R={}
b。添加 P_a, R={[(-∞,-∞),(1,1)]->[P_a],[(1,1), (∞,∞)]->[P_a]} ([(-∞,-∞),(1,1)] 和 [(1,1),(∞,∞)]用对角点定义两个矩形区域)
c。加上P_b，P_b在[(1,1),(∞,∞)]中(也就是说[P_a]可以illuminate P_b), 找到[P_a]中所有可以被P_b照亮的灯塔，即P_a, count+=1, R={[(-∞,-∞),(1,1)]->[P_a,P_b], [(-∞,1),(1,2)]->[P_b],[(1,-∞),(2,1)]->[P_b ],[(1,1),(2,2)]->[P_a,P_b],[(1,2), (2,∞)]->[P_b],[(2,1),(∞,2)]->[P_b],[(2 ,2),(∞,∞)]->[P_a,P_b]}
d.添加P_c，P_c在[(2,2),(∞,∞)]，找到[P_{a,Pb]可以被[Pa,Pb]照亮，也就是Pa， Pb, count+=2, update R (会太长所以这里省略)}

您可能想要表示 R 的一种数据结构是线段树 1 .这里适用的线段树是二维的。我建议你看看现有的帖子，比如 How to code 2D segment tree?并尝试实现自己的。

1 http://en.wikipedia.org/wiki/Segment_tree