自动搬运

查看原文

来自洛谷，原作者为

	看什么看 系统维护，该内容暂不可见。

搬运于2025-08-24 22:37:15，当前版本为作者最后更新于2022-03-23 21:30:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

UPD：

2022/03/29：修复了题目链接（手急打错了），完善了一些语言。

原题链接

P8244 [COCI2013-2014#3] KOLINJE

思路

我们设 $x$ 为最终的答案，$S = \sum\limits_{i=1}^n b_i$，那么题目就是要求找到一个 $[0, 10^7]$ 范围内的浮点数 $x$，使得 $x$ 满足以下不等式组：

$\begin{cases}a_1 + \dfrac{b_1}{S}x \ge a_2 + \dfrac{b_2}{S}x\\\\a_2 + \dfrac{b_2}{S}x \ge a_3 + \dfrac{b_3}{S}x\\\ldots\\a_{n-1} + \dfrac{b_{n-1}}{S}x \ge a_n + \dfrac{b_n}{S}x\end{cases}$

对于不等式：

$a_i + \dfrac{b_i}{S}x \ge a_{i+1} + \dfrac{b_{i+1}}{S}x$

我们将 $\dfrac{b_{i+1}}{S}x$ 移到左边，将 $a_i$ 移到右边，得：

$\dfrac{b_i-b_{i+1}}{S}x \ge a_{i+1}-a_i$

接下来就有三种情况：

Case 1: $b_i > b_{i+1}$

$x \ge \dfrac{S(a_{i+1}-a_i)}{b_i-b_{i+1}}$，此时我们得到了 $x$ 的一个下界。

Case 2: $b_i < b_{i+1}$

$x \le \dfrac{S(a_{i+1}-a_i)}{b_i-b_{i+1}}$，此时我们得到了 $x$ 的一个上界。

Case 3: $b_i = b_{i+1}$

$\begin{cases}a_{i+1}-a_i>0\text{，不等式组无解，直接输出 -1 即可。}\\a_{i+1}-a_i\le0, x \in \mathrm{R}\text{，此时我们什么都不用做。}\end{cases}$

最后判断一下，如果 $x$ 的下界大于 $x$ 的上界，那么也无解。否则输出范围内任意一个 $x$ 即可。

Code：

实现上的一些细节：

1. 注意 $x$ 本来还有一个 $[0,10^7]$ 的范围限制。
2. 要输出多几位小数，要不然精度不够就 WA 了。
3. 我的代码在计算过程中采用分数避免精度问题，如果是用小数实现的要注意细节上的处理。

然后我们就可以愉快地写出以下的代码了：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct node{
	ll fz, fm;
	node (ll x, ll y){
		if (y < 0) y = -y, x = -x; // 把负号存在分子
		fz = x / __gcd(abs(x), y);
		fm = y / __gcd(abs(x), y); // 不约分其实也可以
	}
	bool operator <(const node &a) const {
		return (fz * a.fm < fm * a.fz);
	}
	bool operator >(const node &a) const {
		return (fz * a.fm > fm * a.fz);
	}
};
int n, a[1003], b[1003];
node xmin = node(0, 1), xmax = node(1e7, 1); // x 最开始的上下界
ll S = 0;
int main(){
	scanf ("%d", &n);
	for (int i = 1;i <= n;++i){
		scanf ("%d%d", a+i, b+i);
		S += b[i];
	}
	for (int i = 1;i < n;++i){
		if (b[i] > b[i+1]) xmin = max(xmin, node(S * (a[i+1] - a[i]), b[i] - b[i+1])); // Case 1
		else if (b[i] < b[i+1]) xmax = min(xmax, node(S * (a[i+1] - a[i]), b[i] - b[i+1])); // Case 2
		else if (a[i+1] - a[i] > 0) { // Case 3
			printf("-1");
			return 0;
		}
	}
	if (xmin > xmax) {
		printf("-1");
		return 0;
	}
	printf ("%.10f", (double)xmin.fz / xmin.fm);
	return 0;
}