You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
1.2 KiB
1.2 KiB
POJ 3067 Japan 题目传送门
一、题目描述
两对岸，一边n个点，一边m个点，现在连k条线，问有几个交点。
二、题目解析
梳理一下这其实是一个问逆序对的问题，为什么是逆序对？
举例：
依题意可得上图，算出5个点，除了作图还有什么方法可以得到答案呢？我们不妨先把n的元素看成是有序的，例子就是如此（1 2 3 3）对应的是（4 3 2 1）因为有相同的数据存在，相同位的从小到大排序（4 3 1 2），如果这个结果是（1 2 3 4）的话，是不是就没有交点了，因为没有逆序对存在。
把逆序对互换直到为零，操作步数就是5，其实每添加一条线，增加的点数就是增加的逆序对数，还无法理解就按上述步骤模拟几组数据，明白要干什么。
剩下的就是非常经典的求逆序对问题了。
三、实现代码