题目链接 题意：保证线段之间不包含。 思路：如果这题是输出小数，就是一个很明显的二分！！！难道要直接二分分数？很显然不合理。 二分之后，小数转分数？（无限不循环小数你也转不过去啊） 仔细观察之后会发现一件事，我们总是拿相交的线段对分母才有贡献，因为一个独立线段，直接就是mid/1,其他的就是mid/密集处，那么分母最大就是n。
于是我们很容易用枚举分母的方法AC了这道题！！！注意精度设小一点。
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; struct node { int l,r; } a[N]; int n; bool cmp(node a,node b) { if(a.l!=b.l)return a.l<b.l; return a.r<b.r; } bool judge(double mid) { double pos=0; for(int i=1; i<=n; i++) { if(a[i].l<pos)pos=pos+mid; else pos=a[i].l+mid; if(pos>a[i].r)return 0; } return 1; } int main() { scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d%d",&a[i].l,&a[i].r); sort(a+1,a+n+1,cmp); double l=0,r=1e6,ans=-1; for(int i=1; i<=100; i++) { double mid=(l+r)/2; if(judge(mid))ans=mid,l=mid; else r=mid; } int up=0,down=1; for(int q=1; q<=n; q++) { int p=round(ans*q); if(fabs(p/q-ans)<fabs(up*1.0/down-ans)) { up=p; down=q; } } int g=__gcd(up,down); printf("%d/%d",up/g,down/g); }