P13172 [GCJ 2017 #2] Roller Coaster Scheduling

你设计了一款即将开放的新过山车。它的列车由一排 $N$ 个座位组成，座位从前到后编号为 $1$ 到 $N$。显然，越靠前的座位越有价值。顾客们已经购买了开业当天的门票。每张门票允许特定顾客在特定座位上乘坐一次过山车。有些顾客可能购买了多张门票，他们期望每张门票都能乘坐一次。 你需要决定开业当天需要安排多少次过山车运行。每次运行时，每个座位只能坐一位顾客；某些座位可以空着。你不能让同一位顾客在同一次运行中占据多个座位，也不能让两位顾客在同一次运行中坐在同一个座位上。 你希望通过合理安排，最小化所需的运行次数以满足所有门票。为了减少所需的运行次数，你可以对任意数量的门票进行“晋升”。晋升一张门票意味着将某位顾客的门票换成编号更小（即更靠前）的座位。你希望晋升的门票数量尽可能少，因为晋升太多可能会让顾客变得贪心，今后要求更多晋升。 给定所有已售门票的座位和购买者信息，请你计算：在可以任意晋升门票并最优安排运行的情况下，满足所有门票所需的最少运行次数是多少？以及达到该最少运行次数所需的最少晋升次数是多少？注意，对于同一位顾客在同一次运行中将座位从 $4$ 晋升到 $2$，只算作一次晋升，而不是两次。

输入的第一行包含一个整数 $T$，表示测试用例的数量。接下来有 $T$ 组测试数据。每组测试数据的第一行包含三个整数：$N$（过山车的座位数）、$C$（潜在顾客数）和 $M$（已售门票数）。顾客编号为 $1$ 到 $C$。接下来的 $M$ 行，每行包含两个整数：$P_i$ 表示第 $i$ 张门票对应的座位编号，$B_i$ 表示购买该门票的顾客编号。

对于每个测试用例，输出一行，格式为 `Case #x: y z`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是在允许晋升并最优安排运行的情况下满足所有门票所需的最少运行次数，$z$ 是达到该最少运行次数所需的最少晋升次数。

**样例解释** 注意，最后两个样例不会出现在 Small 数据集。 在第 1 个样例中，两位顾客都购买了第 2 号座位的门票。无法在一次运行中满足两张门票，但如果将其中一张晋升到第 1 号座位，就可以在同一轮中安排两位顾客。 第 2 个样例类似，只不过两张门票都是第 1 号座位。由于无法再晋升，也无法交换到更差的座位，因此只能安排两次运行，每位顾客各一次。 第 3 个样例中，同一位顾客购买了两个座位。由于必须为该顾客安排两次运行，因此无需进行任何晋升。 第 4 个样例中，注意可能存在没有门票的顾客和座位。本例中，第 3 号座位卖出了三张门票。如果将顾客 2 晋升到第 2 号座位，例如，可以安排一次运行：顾客 1 坐第 2 号座位，顾客 3 坐第 3 号座位；再安排一次运行：顾客 2 坐第 2 号座位，顾客 1 坐第 3 号座位。即使再晋升，也无法减少运行次数，因为顾客 1 有两张门票，必须分两次运行，无论座位如何。 第 5 个样例中，一种最优方案是将其中一张 $3\ 1$ 门票晋升到 $1\ 1$。 **数据范围** - $1 \leq T \leq 100$。 - $2 \leq N \leq 1000$。 - $1 \leq M \leq 1000$。 - $1 \leq P_i \leq N$。 - $1 \leq B_i \leq C$。 **Small 数据集（7 分，测试点 1 - 可见）** - $C = 2$。 **Large 数据集（14 分，测试点 2 - 隐藏）** - $2 \leq C \leq 1000$。 由 ChatGPT 4.1 翻译