紫书习题8-14 UVa 1616（二分+小数化分数+精度）

参考了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（二分+小数化分数+精度）

最新文章

热门文章

巴特西

紫书 习题8-14 UVa 1616（二分+小数化分数+精度）

最新文章

热门文章

紫书习题8-14 UVa 1616（二分+小数化分数+精度）