题解：P13396 [GCJ 2010 #1C] Rope Intranet

AFO_Lzx · 2025-07-22 16:09:52 · 题解

要解决本题，我们可以观察到：两根电线会交叉，当且仅当它们的连接方式会交叉。

具体地，对于第 i 根和第 j 根电线，有如下结论：

• 若 a_i<a_j 且 b_i>b_j，这两根电线会交叉。
• 若 a_i>a_j 且 b_i<b_j，这两根电线会交叉。

本质上这就是在计算逆序对的数量。

我们可以通过一下几步解决这个问题：

• 首先先按左侧建筑物的窗户高度 a_i 对电线进行排序。这是保证了对于所有 i<j，有 a_i<a_j。
• 接下来我们根据窗户的新排序就得到了一个新的 b 序列，这里可以通过结构体排序实现。
• 根据前面的结论，我们只需要计算满足 i < j 且 b_i > b_j 的数对 (i,j) 的数量，也就是 b 序列中逆序对的数量。

其中，由于数据范围很小、时限大，所以逆序对的计算只需要 O(n^2) 循环枚举计算即可。

代码如下：

#include<bits/stdc++.h>
using ll = long long;
using namespace std;

const int N = 1e5 + 5;

struct node {
    int a, b;
} c[N];

bool cmp(const node &x, const node &y) {
    return x.a < y.a;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int q;
    cin >> q;

    for (int i = 1; i <= q; i++) {
        int n;
        cin >> n;

        for (int i = 1; i <= n; i++) {
            cin >> c[i].a >> c[i].b;
        }
        sort(c + 1, c + n + 1, cmp);
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) {
                if (c[i].b > c[j].b) cnt++;
            }
        }
        cout << "Case #" << i << ": " << cnt << '\n';
    }
    return 0;
}

省流：我是 Luogu 第 2 个 AC 此题的入。