「POI2018 R3」出租车 Taxis 题解

题目分析

我们有 $n$ 家出租车公司，第 $i$ 家公司的费用函数为 $f_i(d) = s_i + c_i \cdot d$，其中 $d > 0$ 是行程距离。

给定一个排名序列（公司编号的排列），我们需要找到距离 $d > 0$，使得按费用 $f_i(d)$ 排序的结果与给定排名一致（允许相等时任意安排顺序）。

问题转化

设排名为 $r_1, r_2, \ldots, r_n$，其中 $r_i$ 是排在第 $i$ 位的公司编号。

我们需要满足约束条件：

$$f_{r_1}(d) \leq f_{r_2}(d) \leq \cdots \leq f_{r_n}(d) $$

数学建模

相邻位置约束

对于相邻位置 $i$ 和 $i+1$，有：

$$s_{r_i} + c_{r_i} \cdot d \leq s_{r_{i+1}} + c_{r_{i+1}} \cdot d $$

移项得：

$$(c_{r_i} - c_{r_{i+1}}) \cdot d \leq s_{r_{i+1}} - s_{r_i} $$

令 $A = c_{r_i} - c_{r_{i+1}}$，$B = s_{r_{i+1}} - s_{r_i}$，则不等式为 $A \cdot d \leq B$。

分类讨论

根据 $A$ 的符号，分为三种情况：

1. $A = 0$（斜率相等）

   • 如果 $B \geq 0$，则恒成立
   • 如果 $B < 0$，则无解

2. $A > 0$（前一个斜率更大）

   • $d \leq \frac{B}{A}$
   • 需要 $B \geq 0$，否则无解（因为 $d > 0$）

3. $A < 0$（前一个斜率更小）

   • $d \geq \frac{B}{A}$（注意 $A < 0$，不等号方向改变）
   • 如果 $\frac{B}{A} < 0$，则恒成立（因为 $d > 0$）
   • 否则 $d \geq \frac{B}{A}$

算法设计

约束收集与合并

对于排名序列中的每个相邻对 $(r_i, r_{i+1})$：

1. 计算 $A = c_{r_i} - c_{r_{i+1}}$，$B = s_{r_{i+1}} - s_{r_i}$
2. 根据上述规则，得到 $d$ 的一个约束区间
3. 所有约束区间的交集就是可行解集

区间表示与求交

维护两个变量：

• $L$：$d$ 的下界（初始为 $0$，开区间）
• $U$：$d$ 的上界（初始为 $+\infty$）

对于每个约束：

• 如果是上界约束 $d \leq \frac{p}{q}$，则 $U = \min(U, \frac{p}{q})$
• 如果是下界约束 $d \geq \frac{p}{q}$，则 $L = \max(L, \frac{p}{q})$

最终如果 $L < U$ 且存在 $d > 0$ 满足条件，则答案为 $L$ 的下一个有理数（最小正解）。

分数处理

由于答案要以不可约分数输出，我们需要：

1. 用分子分母表示所有分数
2. 实现分数的比较运算
3. 求分数的最小公倍数等运算
4. 输出时约分

关键实现细节

数据结构

struct Company {
    long long s, c;
    int id;
};

struct Fraction {
    long long num, den; // 分子，分母
    
    Fraction(long long n = 0, long long d = 1) : num(n), den(d) {
        normalize();
    }
    
    void normalize() {
        if (den < 0) {
            num = -num;
            den = -den;
        }
        long long g = gcd(abs(num), den);
        num /= g;
        den /= g;
    }
    
    bool operator<(const Fraction& other) const {
        return num * other.den < other.num * den;
    }
    
    // 其他比较运算符...
};

约束处理

void addConstraint(int i, int j, Fraction& L, Fraction& U, bool& feasible) {
    long long A = companies[i].c - companies[j].c;
    long long B = companies[j].s - companies[i].s;
    
    if (A == 0) {
        if (B < 0) feasible = false;
        // B >= 0: 无额外约束
    } else if (A > 0) {
        if (B < 0) {
            feasible = false;
        } else {
            Fraction bound(B, A);
            if (bound < U) U = bound;
        }
    } else { // A < 0
        Fraction bound(B, A);
        if (bound > L) L = bound;
    }
}

寻找最小正解

在得到最终区间 $(L, U)$ 后：

• 如果不可行（$L \geq U$ 或 $U \leq 0$），输出 NIE
• 否则，找到大于 $L$ 的最小有理数

复杂度分析

• 初始构建：$O(n)$ 处理所有相邻约束
• 每次交换：只影响相邻位置的约束，$O(1)$ 更新
• 总体复杂度：$O(n + q)$

优化技巧

1. 局部更新：交换位置 $a$ 和 $b$ 时，只更新 $a-1,a,a+1$ 和 $b-1,b,b+1$ 相关的约束
2. 分数缓存：预处理常用分数的比较结果
3. 提前终止：一旦发现不可行立即返回

示例验证

以样例为例：

公司1: s=8, c=3
公司2: s=12, c=2  
公司3: s=9, c=4
排名: 2, 1, 3

约束：

• (2,1): A=2-3=-1, B=8-12=-4 → d ≥ (-4)/(-1)=4
• (1,3): A=3-4=-1, B=9-8=1 → d ≥ 1/(-1)=-1（恒成立）

最终：$d \geq 4$，最小解 $4/1$

总结

本题的核心是将排名约束转化为线性不等式组，通过维护区间交集来求解。关键在于：

• 正确处理各种斜率情况
• 高效维护分数运算
• 利用交换操作的局部性进行优化

算法标签：数论、分数处理、约束满足、区间求交、贪心