UVa 1616《商队抢劫者》
发布时间
阅读量：
阅读量
题意：
输入n条线段，将每条线段转换为原始线段的一个子线段，确保所有线段长度一致且互不重叠。求出满足条件的最大长度。例如存在3条线段[2,6],[1,4],[8,12]，则最佳方案为 [3.5, 6] [1,3.5][8,10.5]
输出结果为 5 / 2
分析：
该问题的数据处理较为复杂，采用1e-9的精度无法通过测试，唯有将精度设置为1e-10才能正确完成。
解题思路采用二分法进行求解。
此外还涉及小数转化为分数的处理方式。
代码：
#include<bits/stdc++.h>
#define LL long long
#define ms(s) memset(s, 0, sizeof(s))
using namespace std;
const int maxn = 1e5 + 10;
const int m = 1e6 + 5;
const double exp1 = 1e-10;
struct Node {
double l, r;
friend bool operator < (const Node& n1, const Node& n2) {
return n1.l < n2.l || (n1.l == n2.l && n1.r全部评论 (0)
还没有任何评论哟~