P8244 [COCI2013-2014#3] KOLINJE 题解

· · 题解

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}

#### Case 2: $b_i < b_{i+1} #### 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;
}