题解：P11299 [NOISG2021 Finals] Fraud

· · 题解

建议评黄。

本题实际上是让你找到满足条件的正整数 X 和 Y，使得对于任意的 1 \leq i < n，A_i \times X + B_i \times Y > A_{i+1} \times X + B_{i+1} \times Y 都成立。

如果 X 和 Y 可以扩大到正有理数，那么会有以下的结论：

如果 X 和 Y 是符合条件的正有理数，那么对于任意一个正有理数 k，k \times X 和 k \times Y 也是符合条件的。实际上，由上述不等式两边同时乘以 k 即可证明。

那么，我们实际上可以令 X = 1，判断是否存在一个有理数 Y 符合条件即可。

为什么可以这么做？因为 Y 是有理数，所以我们可以假设 Y = \frac{p}{q}，其中 p 与 q 都为正整数。

所以 X = 1 和 Y = \frac{p}{q} 是符合条件的数。根据上述结论，X = q 和 Y = p 也是符合条件的数了（令 k = q 即可）。此时 X 和 Y 都是符合条件的整数了。

好，现在我们令 X = 1，于是我们可以列 n-1 个不等式：

\begin{cases} A_1 + B_1 \times Y > A_2 + B_2 \times Y \\ A_2 + B_2 \times Y > A_3 + B_3 \times Y \\ \cdots \\A_i + B_i \times Y > A_{i+1} + B_{i+1} \times Y \\ \cdots \\ A_{n-1} + B_{n-1} \times Y > A_{n} + B_{n} \times Y\end{cases}

我们拿出其中任意一个不等式组，可以整理得：

(B_i - B_{i+1}) \times Y > A_{i+1} - A_{i}

对其分类讨论：

  1. 当 B_i - B_{i+1} > 0 时: Y > \frac{A_{i+1} - A_{i}}{B_i - B_{i+1}}
  2. 当 B_i - B_{i+1} < 0 时: Y < \frac{A_{i+1} - A_{i}}{B_i - B_{i+1}}
  3. 当 B_i - B_{i+1} = 0 时：如果 A_{i+1} - A_{i} \ge 0，那么输出 NO 即可。

因此，我们可以想到用两个数 (mn,mx) 统计 Y 的下界和上界，最后判断最后的上下界是否合法即可。

如果你想使用 double，注意这道题对精度有很高的要求，建议把 eps 设成 1e-12。

使用 double 的代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a[300005],b[300005];
double mx=1e18,mn=-1e18;//上界与下界 
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
    }
    for(int i=1;i<n;i++){
        if(b[i+1]>b[i]){
            mx=min(mx,(1.0*a[i+1]-1.0*a[i])/(1.0*b[i]-1.0*b[i+1]));
        }else if(b[i+1]<b[i]){
            mn=max(mn,(1.0*a[i+1]-1.0*a[i])/(1.0*b[i]-1.0*b[i+1]));
        }else if(a[i+1]>=a[i]){
            printf("NO\n");
            return 0;
        }
    }
    if(mx-mn<0 || fabs(mx-mn)<1e-12 || mx<1e-12){
        printf("NO\n");     
    }else{
        printf("YES\n");
    }
    return 0;
}

用分数进行处理（避免精度问题）的代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,a[300005],b[300005];//上界与下界 
struct frac{
    ll zi,mu;
}mx,mn;
frac make_frac(ll a,ll b){
    if(b<0)return (frac){-a,-b};
    else return (frac){a,b};
}
frac maxx(frac a,frac b){
    if(a.zi*b.mu-b.zi*a.mu<0)return b;
    else return a;
}
frac minn(frac a,frac b){
    if(a.zi*b.mu-b.zi*a.mu<0)return a;
    else return b;  
}
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&b[i]);
    }
    mx={1000000000,1};
    mn={-1000000000,1};
    for(int i=1;i<n;i++){
        if(b[i+1]>b[i]){
            mx=minn(mx,make_frac(a[i+1]-a[i],b[i]-b[i+1]));
        }else if(b[i+1]<b[i]){
            mn=maxx(mn,make_frac(a[i+1]-a[i],b[i]-b[i+1]));
        }else if(a[i+1]>=a[i]){
            printf("NO\n");
            return 0;
        }
    }
    if(mx.zi*mn.mu-mn.zi*mx.mu<=0 || mx.zi<=0){
        printf("NO\n");     
    }else{
        printf("YES\n");
    }
    return 0;
}