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.
22 lines
1.2 KiB
22 lines
1.2 KiB
POJ 3067 Japan
|
|
[题目传送门](http://poj.org/problem?id=3067)
|
|
|
|
### 一、题目描述
|
|
两对岸，一边$n$个点，一边$m$个点，现在连$k$条线，问有几个交点。
|
|
|
|
### 二、题目解析
|
|
梳理一下这其实是一个问逆序对的问题，为什么是逆序对？
|
|
|
|
举例：
|
|
<img src='https://img-blog.csdn.net/2018073016441752?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vc2NyZWFk/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70'>
|
|
|
|
依题意可得上图，算出$5$个点，除了作图还有什么方法可以得到答案呢？我们不妨先把$n$的元素看成是有序的，例子就是如此（$1$ $2$ $3$ $3$）对应的是（$4$ $3$ $2$ $1$）因为有相同的数据存在，相同位的从小到大排序（$4$ $3$ $1$ $2$），如果这个结果是（$1$ $2$ $3$ $4$）的话，是不是就没有交点了，因为没有逆序对存在。
|
|
|
|
把逆序对互换直到为零，操作步数就是$5$，其实每添加一条线，增加的点数就是增加的逆序对数，还无法理解就按上述步骤模拟几组数据，明白要干什么。
|
|
|
|
剩下的就是非常经典的求逆序对问题了。
|
|
|
|
### 三、实现代码
|
|
```c++
|
|
|
|
``` |