题目链接：https://vjudge.net/problem/UVA-1616
大意：输入n个区间，把它们分成等长的、互不相交的子区间，求子区间的最大长度。
思路：二分答案，再小数化分数即可。
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<iostream> using namespace std; const int maxn = 1e6 + 10; const double eps = 1e-9; int n; struct Node { int l, r; bool operator < (const Node& rhs) const { return l < rhs.l || l == rhs.l && r < rhs.r; } }C[maxn]; bool judge(double mid) { double cur = 0; for(int i = 0; i < n; i++) { double r = max(cur, (double)C[i].l) + mid; if(r > C[i].r) return false; cur = r; } return true; } int main() { while(scanf("%d",&n) == 1) { for(int i = 0; i < n; i++) scanf("%d%d",&C[i].l, &C[i].r); sort(C, C+n); double l = 0.0, r = 1000000.0; while(r - l > eps) { double mid = (l + r) / 2.0; if(judge(mid)) l = mid; else r = mid; } double ans = l; int rp = 0, rq = 1; for(int p, q = 1; q <= n; q++) { p = round(ans * q); if(fabs((double)p/q - ans) < fabs((double)rp/rq - ans)) { rp = p; rq = q; } } printf("%d/%d\n", rp, rq); } return 0; }
