P11709 「KTSC 2020 R2」魔法转盘

**请使用 C++17 或 C++20 提交本题** 你需要在程序开头加入如下代码： ```cpp #include long long findMinClicks(int M, int R, std::vector P); ``` 题目译自 [2020년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사](https://www.ioikorea.kr/archives/ioitst/2020/) T1「 [마법의 다이얼](https://assets.ioikorea.kr/ioitst/2020/1/dial/dial_statement.pdf)」

在持续的算法学习中感到疲惫的京根，想去另一个世界休息几天。有一天，他听说了一个通往另一个世界的门的位置，于是他去了那里。那里有一扇通往另一个世界的门，但门被锁住了，门上有一个巨大的转盘锁。 这个锁由上下排列的 $M$ 个转盘组成。每个转盘有 $R$ 个格子，可以左右旋转到不同的格子。每个格子上可能有一个点，也可能没有点。每个转盘至少有一个点。通过旋转转盘，使得在某个位置上所有格子都垂直对齐有点，门就会打开。每个转盘可以单独旋转。由于转盘非常重，旋转起来很费力，所以希望旋转的总格子数最少。  上图展示了一个转盘的例子。最佳方法之一是：将第一个转盘向左旋转一格，第二个转盘向左旋转两格，第三个转盘向右旋转一格，第四个转盘不旋转，总共旋转 $4$ 格。 给定转盘的大小和点的位置，编写一个程序，计算最少需要旋转多少格才能打开门。点的位置由转盘编号和格子编号的坐标表示。最上面的转盘是 $0$ 号转盘，向下编号依次增加，最下面的转盘是 $M-1$ 号转盘。为了确定格子编号，任意相同位置的（即垂直对齐的）格子编号为 $0$，向右编号依次增加。$0$ 号格子的左边是 $R-1$ 号格子。给定的点的坐标不会重复。 你需要实现以下函数： `long long findMinClicks(int M, int R, vector< pair > P);` - 参数 $M$ 是转盘的数量。 - 参数 $R$ 是每个转盘的格子数。 - 参数 $P$ 是一个包含 $N$ 个整数对的数组。每个整数对的第一个数是转盘编号，第二个数是格子编号。给定的点的坐标不会重复。 - 函数 `findMinClicks()` 返回打开门所需的最少旋转格子数。 该函数应按照上述描述工作。当然，你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。

示例评测程序按以下格式读取输入： - 第 $1$ 行：整数 $N\,M\,R$ - 第 $2 \sim N+1$ 行：整数 $D_{i}\,C_{i}$，其中 $(D_{i}, C_{i})$ 是第 $i$ 个点的坐标。

示例评测程序将输出你的代码中 `findMinClicks()` 函数返回的值。

对于所有输入数据，满足： - $1 \leq R \leq 10^{9}$ - $1 \leq N \leq \min(MR, 5\cdot 10^5)$ - $1 \leq M \leq N$ 详细子任务附加限制及分值如下表所示。 | Subtask | 分值 | 约束 | | :----------: | :----------: | :----------: | |$1$|$10$|$1 \leq N \leq 5000,1 \leq R \leq 5000$| |$2$|$15$|$1 \leq M \leq 5000,1 \leq R \leq 5000$| |$3$|$16$|$1 \leq N \leq 5000$| |$4$|$109$|无附加限制| 本题满分为 $150$ 分。