一、题意

输入n条线段，线段之间没有包含关系，要求你把每条线段截成原来的一条子线段，使得改变之后的所有线段长度相等且互不相交（端点可以重合）。求每条线段的最大长度，并用分数表示。

二、解析

刚看到要用分数表示时，我是很懵的，但后来仔细一想，其实这只是出题人的虚晃一枪，我们首先求出小数解，然后再转变为分数即可。

如何求得小数解呢？我们很容易发现，这道题直接求出最大解很难，但是判定某个解是否符合题意是容易的，因此这就很容易让我们想到之前讲过的“二分答案”法。之前的二分答案是二分整数值，这道题只要二分double值即可，这样其实简单的多，不需要许多细节处理，唯一要注意的就是double值之间不能直接判定相等，必须只用fabs()结合设定一个常数精度值eps来实现。具体见代码。

三、代码

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 100000 + 5;
const double INF = 1e6 + 5, eps = 1e-10;
struct section {
    int l, r;
    bool operator < (const section& rhs) const {
        return l < rhs.l;
    }
} a[maxn];
int n;

bool isOK(double len) {
    double r = -INF;  // 维护一个“上一线段的右端值”
    for(int i = 0; i < n; i ++) {
        r = max(r, (double)a[i].l) + len;
        if(r > a[i].r) return 0;  // 超过线段原右端值则说明该长度失败
    }
    return 1;
}

void output(double d) {  // 小数转分数输出的方法
    int ans_p = INF, ans_q = 1;
    for(int q = 1; q <= n; q ++) {
        int p = (int)(d * q + 0.5);
        if(fabs((double)ans_p / ans_q - d) > fabs((double)p / q - d)) ans_p = p, ans_q = q;
    }
    cout << ans_p << "/" << ans_q << endl;
}

int main() {
    while(cin >> n) {
        for(int i = 0; i < n; i ++) cin >> a[i].l >> a[i].r;
        sort(a, a + n);
        double l = 0, r = INF;
        while(fabs(l - r) > eps) {  // 二分答案，double要用fabs进行精度控制
            double mid = (l + r) / 2;
            if(isOK(mid)) l = mid;
            else r = mid;
        }
        output(l);
    }
}

四、归纳

  • 二分答案也可以在double类型的基础上进行，与整数二分的区别：
    • 无需考虑细节
    • double值（l、r）之间不能直接判定相等，必须只用fabs()结合设定一个常数精度值eps来实现
  • 看到输出分数不要慌张，小数通过枚举分母的方法可以轻松转变为分数，当然是否通过小数转换的方式还得具体题目具体分析
  • 看到直接求解困难，但是判定容易的题目，可以考虑使用二分答案法