习题8-14 商队抢劫者（Caravan Robbers ACMICPC NEERC 2012 UVa1616）
二分+贪心
题目描述：有n个区间，选择各区间的子区间使得各个子区间不相交，而且子区间的长度相同，求最大子区间的长度。
解题思路：二分枚举子区间长度，用贪心法判断该子区间是否满足题意。最后一步是将所得的浮点数化成分数。另外，本题对精度卡的特别严，1e-6都不行，1e-9可行。
代码如下：
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
struct Interval
{
int l,r;
Interval(int a,int b):l(a),r(b){}
Interval(){}
bool operator <(const Interval b) const
{
return l==b.l?r<b.r:l<b.l;
}
};
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
const int maxn=100000+10;
const double esp=1e-6;
int n;
Interval gang[maxn] ;
int main()
{
//freopen("in.txt","r",stdin);
while(cin >> n)
{
int a,b,ri=-1;
for(int i=0;i<n;i++)
{
scanf("%d %d",&gang[i].l,&gang[i].r);
ri=max(gang[i].r,ri);
}
sort(gang,gang+n);
double left=0,right=(double)ri;
while(right-left>esp)
{
double mid=(right+left)/2,cur=0;
bool is_ok=true;
for(int i=0;i<n;i++)//贪心
{
if(cur<(double)gang[i].l) cur=gang[i].l;
if(cur+mid<(double)gang[i].r-esp)
{
cur+=mid;
}
else
{
is_ok=false;
break;
}
}
if(is_ok) left=mid;
else right=mid;
}
int deno=1,nume=0;//将浮点数转换为分数
for(int i=1;i<=n;i++)
{
int x=round(left*i);
if(fabs((double)x/i-left)<fabs((double)nume/deno-left))
{
nume=x;
deno=i;
}
}
int g=gcd(nume,deno);//此题不求最大公约数也是对的。
printf("%d/%d\n",nume/g,deno/g);
}
return 0;
} 本题中将浮点数转化成分数是个技巧，因为总共有n个区间，最极限的情况下是这n个区间完全相同，这时最大子区间长度就是left/n，所以说循环的上限到n就行。另外需要注意的是什么时候强制类型转换等细节问题。
