题解：P8244 [COCI2013-2014#3] KOLINJE

· · 题解

题目传送门

转化一下题意，可得： 我们要找到一个数 k ，使得其满足 n-1 个不等式：

\sum_{i=1}^{n-1} a_i+b_{i}\times k \geq a_{i+1} +b_{i+1} \times k

移一下项：

\sum_{i=1}^{n-1} a_i-a_{i+1} \geq (b_{i+1} - b_i)\times k

可以发现，我们只需要把每一个不等式处理出来，取并集就是 k 的解集；

又因他要最小的，取下界即可；

考虑如何解一个不等式：

  1. b_{i+1} - b_i > 0$，有 $ k \le \frac{a_i-a_{i+1}}{b_{i+1} - b_i}
  2. b_{i+1} - b_i < 0$,有 $k \ge \frac{a_i-a_{i+1}}{b_{i+1} - b_i}
  3. b_{i+1} - b_i = 0$,有 $a_i-a_{i+1} \ge 0

（其实就是模拟解不等式的过程）

注意事项：

  1. 精度问题；
  2. 一定要考虑 b_{i+1} - b_i = 0 的情况；
  3. 像解不等式组，也有上界小于下界的情况，无解；
  4. 最后的答案是 k\times \sum_{i=1}^n b_i;

code

#include <bits/stdc++.h>//万能头文件
using namespace std;
inline long long read(){//快读
    long long x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*f;
}
const int N=1e3+5;
int n;
int a[N],b[N];
int da[N],db[N];
int32_t main(){
//  ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
//  freopen("huo.in","r",stdin);
//  freopen("huo.out","w",stdout);
    n=read();
    long double sum=0;
    long double L=0,R=1e9;
    for(int i=1;i<=n;i++)a[i]=read(),b[i]=read(),sum+=b[i];
    for(int i=1;i<n;i++){
        da[i]=a[i]-a[i+1];
        db[i]=b[i+1]-b[i];
        if(db[i]>0){
            R=min(R,(long double)da[i]/db[i]);
        }else if(db[i]<0){
            L=max(L,(long double)da[i]/db[i]);
        }else{
            if(da[i]<0)return puts("-1"),0;
        }
    }
    if(R<L)return puts("-1"),0;
    cout<<fixed << setprecision(12) << L*sum;
    return 0;
}

完结撒花