参考了https://www.cnblogs.com/dwtfukgv/p/5645446.html
(1)直接二分答案。说实话我没有想到, 一开始以为是贪心, 以某种策略能得到最优解。
但是想了很久没想出来, 后来看了博客发现因为显然答案是单调的, 可以用二分来做。
看到最大, 最小, 可以考虑答案是否单调, 单调考虑用二分
(2)然后是小数化分数, 其实一开始我想模拟分数, 然后发现很麻烦, 之后博客里的方法技巧性很强。
其实这个方法默认了分母是在1到n之间的, 而好像题目并没有给出这个条件。这个其实就是枚举所有
与ans接近的分数, 选最近的。
(3)这道题目的精度太恐怖了, 第一是1e-9, 第二是我为了保险最后ans取得是最后的(l+r)/2。
但是wa, 改成ans=l就过了……
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
const int MAXN = 112345;
const double EPS = 1e-9;
struct node
{
int l, r;
bool operator < (const node& x) const
{
return l < x.l;
}
}a[MAXN];
int n;
bool judge(double key)
{
double start = 0;
REP(i, 0, n)
{
if(start < a[i].l) start = a[i].l;
if(start + key > a[i].r) return false;
start += key;
}
return true;
}
int main()
{
while(~scanf("%d", &n))
{
REP(i, 0, n) scanf("%d%d", &a[i].l, &a[i].r);
sort(a, a + n);
double l = 0, r = 1e6;
while(r - l > EPS)
{
double m = (l + r) / 2.0;
if(judge(m)) l = m;
else r = m;
}
double ans = l;
int ansp = 0, ansq = 1;
REP(q, 1, n + 1)
{
int p = round(ans * q);
if(fabs((double)p / q - ans) < fabs((double)ansp / ansq - ans))
ansp = p, ansq = q;
}
printf("%d/%d\n", ansp, ansq);
}
return 0;
}
紫书 习题8-14 UVa 1616(二分+小数化分数+精度)的更多相关文章
-
紫书 习题 11-9 UVa 12549 (二分图最小点覆盖)
用到了二分图的一些性质, 最大匹配数=最小点覆盖 貌似在白书上有讲 还不是很懂, 自己看着别人的博客用网络流写了一遍 反正以后学白书应该会系统学二分图的,紫书上没讲深. 目前就这样吧. #includ ...
-
紫书 习题 11-8 UVa 1663 (最大流求二分图最大基数匹配)
很奇怪, 看到网上用的都是匈牙利算法求最大基数匹配 紫书上压根没讲这个算法, 而是用最大流求的. 难道是因为第一个人用匈牙利算法然后其他所有的博客都是看这个博客的吗? 很有可能-- 回归正题. 题目中 ...
-
紫书 习题8-12 UVa 1153(贪心)
本来以为这道题是考不相交区间, 结果还专门复习了一遍前面写的, 然后发现这道题的区间是不是 固定的, 是在一个范围内"滑动的", 只要右端点不超过截止时间就ok. 然后我就先考虑有 ...
-
紫书 习题8-7 UVa 11925(构造法, 不需逆向)
这道题的意思紫书上是错误的-- 难怪一开始我非常奇怪为什么第二个样例输出的是2, 按照紫书上的意思应该是22 然后就不管了,先写, 然后就WA了. 然后看了https://blog.csdn.net/ ...
-
紫书 习题 11-10 UVa 12264 (二分答案+最大流)
书上写的是UVa 12011, 实际上是 12264 参考了https://blog.csdn.net/xl2015190026/article/details/51902823 这道题就是求出一种最 ...
-
紫书 习题 11-17 UVa 1670 (图论构造)
一开始要符合题目条件, 那么肯定没有任何一个点是孤立的, 也就是说没有点的度数是1 所以我就想让度数是1的叶子节点相互连起来.然后WA 然后看这哥们的博客 https://blog.csdn.net/ ...
-
紫书 习题 8-23 UVa 1623 (set妙用 + 贪心)
这道题我是从样例中看出思路了 2 4 0 0 1 1 看这组数据, 输出的是No, 为什么呢?因为两个1之间没有神龙喝水, 所以一定会有水灾. 然后就启发了我,两次同一个湖的降水之间必须至少有一次神龙 ...
-
紫书 习题 8-21 UVa 1621 (问题分析方法)
知道是构造法但是想了挺久没有什么思路. 然后去找博客竟然只有一篇!!https://blog.csdn.net/no_name233/article/details/51909300 然后博客里面又说 ...
-
紫书 习题8-18 UVa 11536 (扫描法)
这道题貌似可以用滑动窗口或者单调栈做, 但是我都没有用到. 这道题要求连续子序列中和乘上最小值最大, 那么我们就可以求出每一个元素, 以它为最小值的的最大区间的值, 然后取max就ok了.那么怎么求呢 ...
随机推荐
-
ansible高级用法
将多个符合正则的文件拷贝到目标机器 - name: Copy copy: src={{ item }} dest=/root/.sshkeys mode=0600 owner=root group=r ...
-
移植net-snmp到开发板(mini210)
1.安装交叉编译工具arm-linux-gcc 2.下载net-snmp源码安装包 3.解压安装包 4../configure --build=i686-linux --host=arm-linux ...
-
Android从入门到精通pdf+书源代码
不须要积分,免费放送 Android从入门到精通的pdf,入门的好书籍,因为csdn文件大小的限制所以分成了两部分. part1地址:http://download.csdn.net/detail/a ...
-
java基础复习之对于String对象,能够使用“=”赋值,也能够使用newkeyword赋值,两种方式有什么差别?
String类型是实际工作中经经常使用到的类型,从数据类型上划分,String是一个引用类型,是API中定义的一个类.所以String类型的对象能够用new创建,比如String name=new S ...
-
webpack之代码分离
https://robertknight.github.io/posts/webpack-dll-plugins/ webpack一般会把一个文件里import/require的文件都会打包在一起,最 ...
-
Redis学习-LUA脚本
最近在做K线的项目中,需要计算商品的分时数据.为了保证多台机器对同一商品的计算的有序性,所以在Redis中进行计算,同时为了保证在分时数据计算过程的原子性所以使用了LUA脚本,Redis内置了对LUA ...
-
21 viewPager--- hzScrollView ----llContainer
结构: MainActivity.java package com.qf.day21_hsviewpagerfragment_demo5; import java.util.ArrayList; im ...
-
Linux下使用GDAL进行开发(automake使用)
首先写三个源代码文件,分别是GDALTest.cpp.Fun.cpp和Fun.h,将这三个存放在一个叫GDALTest的文件夹中,然后打开终端,切换到该目录,如下图所示(注:这个图是最后截图的,所以文 ...
-
react canvas圆环动态百分比
import React from 'react'; import Tools from '../../tools/index' export default class PercentageRing ...
-
bfs-poj3278
题目链接:http://poj.org/problem?id=3278 题意:农夫原始在N位置上,他的目的是要抓到在K位置上的牛.牛的位置是固定不变的,而农夫的移动是在一条水平线上进行的,移动方式有以 ...