自动搬运

查看原文

来自洛谷，原作者为

	reinforest ด้้้้้็้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้้้้้้็็็็็้้้้้็็็็็้ (？

搬运于2025-08-24 23:06:12，当前版本为作者最后更新于2025-01-13 21:33:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

建议评黄。

本题实际上是让你找到满足条件的正整数 $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;
}