UVa 1616 Caravan Robbers (二分+贪心)
二分 贪心 UVa
2023-09-11 14:17:19 时间
题意:给定 n 个区间,然后把它们变成等长的,并且不相交,问最大长度。
析:首先是二分最大长度,这个地方精度卡的太厉害了,都卡到1e-9了,平时一般的1e-8就行,二分后判断是不是满足不相交,找出最长的。这个题并不难,
就是精度可能控制不好,再就是把小数化成分数时,可能有点麻烦。
代码如下:
#include <iostream> #include <cmath> #include <cstdlib> #include <set> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int INF = 0x3f3f3f3f; const double eps = 1e-9;//注意精度 const int maxn = 1e5 + 5; struct node{ int l, r; bool operator < (const node &p) const{ return r < p.r; } }; node a[maxn]; int n; int main(){ // freopen("in.txt", "r", stdin); while(scanf("%d", &n) == 1){ for(int i = 0; i < n; ++i) scanf("%d %d", &a[i].l, &a[i].r); double r = 1000000, l = 0, ans = 0; sort(a, a+n); while(r - l > eps){//二分 double m = ((l+r)/2.0); bool ok = true; double s = 0; for(int i = 0; i < n; ++i){//贪心 if(s < a[i].l) s = a[i].l; if(s + m > a[i].r){ ok = false; break; } s += m; } if(ok){ ans = m; l = m; } else r = m; } 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; }
相关文章
- 33. 搜索旋转排序数组,二分查找某个数
- poj 3273 Monthly Expense (二分)
- Java实现 LeetCode 704 二分查找(二分法)
- Java实现二分图的最大权匹配
- Java实现二分图的最大权匹配
- Java实现二分查找(折半查找)
- 重新整理数据结构与算法—— 二分查找法[十二]
- (算法:二分查找)在排序数组中,找出给定数字出现的次数
- LeetCode-878. 第 N 个神奇数字【数学,二分查找,找规律】
- hdu2444 The Accomodation of Students(推断二分匹配+最大匹配)
- [LeetCode] 74. 搜索二维矩阵 ☆☆☆(二分查找)
- 二分变种
- 算法——二分查找
- POJ 1274 The Perfect Stall 水二分匹配
- POJ 1422 Air Raid(二分图匹配最小路径覆盖)
- PAT 1044 Shopping in Mars[二分][难]
- 【1-2数组】704. 二分查找算法
- 790. 数的三次方根(实数二分)