题目链接

题目大意

有 $N$ 名参赛者，每人有两轮得分 $A_i$（第一轮）和 $B_i$（第二轮）。需选择正整数权重 $X$ 和 $Y$，使得所有参赛者的最终得分严格按原顺序递减。 最终，对任意 $1 \leq i < j \leq N$，都满足 $S_i > S_j$，其中最终得分公式为：

判断是否存在这样的 $X$ 和 $Y$。

思路分析

只需满足相邻参赛者的约束。

因为得分的递减具有传递性（若 $S_1 > S_2$ 且 $S_2 > S_3$，则 $S_1 > S_3$。），所以只需保证所有相邻参赛者 $i$ 和 $i+1$ 满足 $S_i > S_{i+1}$，就能满足全局条件。

不等式转化。

• 对相邻参赛者 $i$ 和 $i+1$，代入得分公式得：

• 提公因式：

• 令 $x1 = A_i - A_{i+1}$，$x2 = B_i - B_{i+1}$，不等式变形为：

用比值消元。

由于 $X$、$Y$ 是正整数，定义比值 $k = \frac{X}{Y}$（$k$ 是正实数），两边同时除以 $Y$，则不等式进一步变形为：

此时问题转化为：是否存在正实数 $k$，满足所有相邻对的上面的不等式。

分情况约束 $k$ 的范围。

• 若 $x1 = 0$：不等式变形为 $x2 > 0$。若 $x2 \leq 0$，无解；否则不影响 $k$ 的范围。
• 若 $x1 > 0$：不等式变形为 $k > -\frac{x2}{x1}$，更新 $k$ 的下限 $l = \max(l, -\frac{x2}{x1})$。
• 若 $x1 < 0$：不等式变形为 $k < -\frac{x2}{x1}$（除以负数，不等号反转），更新 $k$ 的上限 $r = \min(r, -\frac{x2}{x1})$。

判断合法性。

若所有相邻对约束后，$k$ 的范围仍非空（用 $l < r - eps$ 判定），则存在对应的正整数 $X$ 和 $Y$，输出 YES；否则输出 NO。

AC Code

不要抄袭

#include<bits/stdc++.h>
using namespace std;

const double eps=1e-12;
int N;
long long A[5201314];
long long B[5201314];
bool f=true;//标记是否存在合法解，初始为true
double l=0.0;
double r=1e18;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> N;
	for(int i=0;i<N;i++) cin >> A[i];
	for(int i=0;i<N;i++) cin >> B[i];
	
	//遍历所有相邻参赛者对，约束k的范围
	for(int i=0;i<N-1;i++)
	{
		//计算相邻两人的得分差：x1=A[i]-A[i+1], x2=B[i]-B[i+1]
		long long x1=A[i]-A[i+1];
		long long x2=B[i]-B[i+1];
		
		//情况1：x1=0，不等式简化为x2>0
		if(x1 == 0)
		{
			//若x2<=0，无合法解，标记为false并退出循环
			if(x2 <= 0)
			{
				f=false;
				break;
			}
			//x2>0，该条件不约束k，跳过后续处理
			continue;
		}
		
		//计算临界值k0=-x2/x1（不等式x1*k+x2>0的边界）
		double k0=-(double)x2/x1;
		
		//情况2：x1>0，要求k>k0，更新下限l
		if(x1 > 0)
			l=max(l,k0);
		//情况3：x1<0，要求k<k0，更新上限r
		else
			r=min(r,k0);
		
		//检查当前k的范围是否合法
		if(l+eps >= r)
		{
			f=false;
			break;
		}
	}
	
	//最终判断：若标记为true且k的范围非空，输出YES，否则输出NO
	if(f && l<r-eps)
		cout << "YES";
	else
		cout << "NO";
	
	return 0;
}