野人山洞问题题解

问题分析

我们需要找到一个最小的山洞数$M$，使得在$n$个野人的有生之年（即他们各自的寿命$L_i$年内），没有任何两个野人会在同一年住在同一个山洞中。

野人的移动规律是环形的：每年第$i$个野人从当前山洞沿顺时针方向前进$P_i$个山洞。山洞编号是模$M$的循环。

关键思路

1. 问题转化

对于任意两个野人$i$和$j$，我们需要确保在他们共同存活的年限内（即前$\min(L_i, L_j)$年），他们不会相遇在同一个山洞。

野人$i$在第$t$年的位置为：$C_i + P_i \times t \pmod{M}$ 野人$j$在第$t$年的位置为：$C_j + P_j \times t \pmod{M}$

他们相遇的条件是：

$$C_i + P_i \times t \equiv C_j + P_j \times t \pmod{M} $$

整理得：

$$(P_i - P_j) \times t \equiv C_j - C_i \pmod{M}$$

2. 数学建模

对于每对野人$(i,j)$，我们需要检查在$t = 0, 1, 2, \dots, \min(L_i, L_j)$年内，上述同余方程是否有解。

如果对于所有野人对，该方程在$t \leq \min(L_i, L_j)$时都无解，则当前$M$是可行的。

3. 算法选择

由于$n \leq 15$，我们可以枚举所有野人对，对于每个候选的$M$，检查是否满足条件。

算法详解

核心函数 check2()

bool check2() {
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            if (p[i] == p[j])  // 速度相同的情况特殊处理
                continue;  
            
            int x, y;
            // 统一处理，确保y为正数
            if (p[i] < p[j])  
                x = (c[i] - c[j] + m) % m, y = p[j] - p[i];
            else
                x = (c[j] - c[i] + m) % m, y = p[i] - p[j];
            
            int _ = min(l[i], l[j]);  // 共同存活年数
            
            // 检查在共同存活期内是否会相遇
            for (int k = 0; k <= y - 1; k++) {
                int now = x + k * m;
                if (now > y * _)  // 超过共同存活期
                    break;
                if (now % y == 0)  // 找到整数解，说明会相遇
                    return 0;
            }
        }
    return 1;
}

数学原理详解

对于同余方程：

$$(P_i - P_j) \times t \equiv C_j - C_i \pmod{M}$$

设$d = P_i - P_j$，$b = C_j - C_i$，则方程为：

$$d \times t \equiv b \pmod{M}$$

这个方程等价于：

$$d \times t + M \times k = b \quad (k \in \mathbb{Z}) $$

由于我们只关心$t$在$[0, \min(L_i, L_j)]$范围内是否有解，可以枚举可能的$t$值来检查。

特殊情况处理

1. 当$P_i = P_j$时：

   • 如果$C_i = C_j$，则初始就在同一山洞，直接冲突
   • 如果$C_i \neq C_j$，则永远保持相同距离，不会相遇

2. 模运算处理：

   • 使用(c[i] - c[j] + m) % m来确保结果为非负数

完整代码分析

#include <bits/stdc++.h>
using namespace std;
const int N = 20;        
int n, m, t;             
int c[N], p[N], l[N];  

// 检查当前山洞数m是否满足条件
bool check2() {
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++) {
            if (p[i] == p[j])
                continue;  
            
            int x, y;
            if (p[i] < p[j])  
                x = (c[i] - c[j] + m) % m, y = p[j] - p[i];
            else
                x = (c[j] - c[i] + m) % m, y = p[i] - p[j];
            
            int _ = min(l[i], l[j]);
            
            for (int k = 0; k <= y - 1; k++) {
                int now = x + k * m;
                if (now > y * _)
                    break;
                if (now % y == 0) 
                    return 0;
            }
        }
    return 1;
}

int main() {
    scanf("%d", &n);
    
    // 读入数据并初始化
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", c + i, p + i, l + i);
        m = max(m, c[i]);  // 山洞数至少为最大初始洞穴编号
        t = max(t, l[i]);  // 记录最大寿命
    }
    
    // 从最小可能值开始枚举山洞数
    for (;; m++) {
        if (check2()) { 
            printf("%d", m);
            return 0;
        }
    }
    
    return 0;
}

复杂度分析

• 时间复杂度：最坏情况下需要枚举到$M = 10^6$，对于每个$M$检查$C_n^2 = 105$对野人，每对检查最多$\min(P_i, P_j)$次，总体可接受
• 空间复杂度：$O(n)$，只存储野人信息

样例验证

对于样例：

n = 3
野人1: C=1, P=3, L=4
野人2: C=2, P=7, L=3  
野人3: C=3, P=2, L=1

程序从$M = \max(C_i) = 3$开始枚举，当$M = 6$时满足所有条件：

• 野人1和野人2在3年内不会相遇
• 野人1和野人3在1年内不会相遇
• 野人2和野人3在1年内不会相遇

因此输出$6$。

算法优化点

1. 提前终止：当发现任何一对野人会在共同存活期内相遇时，立即返回
2. 下界优化：从最大初始洞穴编号开始枚举，避免不必要的检查
3. 特殊情况处理：对速度相同的野人进行特殊处理，提高效率

该算法充分利用了数据范围的特点，在可接受的时间内找到了最优解。