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

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

具体地，对于第

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)

循环枚举计算即可。

代码如下：

CPP

#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 此题的入。

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

文章操作

相关推荐

评论

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