1616 - Caravan Robbers 【二分】

本文主要是介绍1616 - Caravan Robbers 【二分】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

传送门

给出n条线段的起点和终点
找出n条线段中的一个片段，使得片段长度一样并且不相交
求片段的最大长度，最后的结果要以分数的形式给出

样例

input

3
2 6
1 4
8 12

output

5/2

解释

三条线段分别为2~6 1~4 8~12
找出的片段的最大值为5/2，片段的长度分别为1~7/2 7/2~6 8~21/2

思路

• step1: 二分片段长度，用小数

• step2: 其数据量的最大值为100000，所以可以枚举分母的大小，求出相应的分子，计算分子/分母的最小误差，输出即可

代码

#include<cstdio>
#include<map>
#include<queue>
#include<cstring>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include <math.h>
using namespace std;const int maxn = 100000 + 5;
const double eps = 1e-10;
int n;int gcd(int a,int b)
{return !b? a : gcd(b,a%b);
}int doublecmp(double a,double b)
{if(fabs(a-b)<eps) return 0;if(a>b) return 1;return -1;
}struct Line
{double l,r;bool operator < (const Line L){if(r==L.r) return l<L.l;else return r<L.r;}
} L[maxn];bool ok(double mid)
{double l=0;for(int i=0; i<n; i++){l = max(l,L[i].l);if(doublecmp(l+mid , L[i].r)==1) return false;l = l + mid;}return true;
}int main()
{while(~scanf("%d",&n)){double max_len = 0;for(int i=0; i<n; i++){scanf("%lf %lf",&L[i].l,&L[i].r);max_len = max(max_len,L[i].r-L[i].l);}sort(L,L+n);double l = 0;double r = max_len;double mid;while(r-l>eps){mid = (l+r)/2;if(ok(mid)) l = mid;else r = mid;}mid = (l+r)/2;int fz;int fm;double er=maxn;for(int i=1; i<=maxn-5; i++) //枚举分母{int j = floor(i*mid); //向前取一位if( doublecmp(er,fabs(mid - 1.0*j/i)) == 1 ){er = fabs(mid - 1.0*j/i);fz = j;fm = i;}j = ceil(i*mid);//向后取一位if( doublecmp(er,fabs(mid - 1.0*j/i)) == 1 ){er = fabs(mid - 1.0*j/i);fz = j;fm = i;}}int g = gcd(fz,fm);fz /= g;fm /= g;printf("%d/%d\n",fz,fm);}
}
/*
3
2 6
1 4
8 12
3
1 1000
1 1000
1 10005/2
333/1
*/

Hit

在计算误差的时候，j = i*mid; 这一步中需要向下取值使用函数floor(); 并且向下取值ceil();

这篇关于1616 - Caravan Robbers 【二分】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---