自动搬运

查看原文

来自洛谷，原作者为

	Unordered_OIer **

搬运于2025-08-24 22:29:53，当前版本为作者最后更新于2021-03-20 18:50:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

P7441 题解

这道题的思维难度还是有的。

Description

给定两个整数 $x,y$ 和一个正整数 $K$，生成了一个长度为 $\infty$ 的序列 $C,E$，满足：

$$C_i=\begin{cases} x \times i & x \times i \leq K\\-K & \text{otherwise}\end{cases} $$$$E_i=\begin{cases} y \times i & y \times i \leq K\\-K & \text{otherwise}\end{cases} $$

需要选择 $m$ 对 $C_i,E_j$ 满足 $C_i + E_j \geq K$，选择一次后所选择的 $C_i,E_j$ 都不可再用，问 $m$ 的最大值。

一共有 $T$ 组这样的数据

Solution

观察一下数据范围，$1 \leq K \leq 10^{10},0 \leq x,y \leq 10^{10}$，所以单次询问算法复杂度肯定是 $\mathcal O(1)$ 级别的，于是考虑数学。

首先这个 $\infty$ 长度是假的，因为负数 $+$ 负数一定不会 $\geq K$，所以有效的 $C_i,E_j$ 分别有 $\left\lfloor \dfrac{K}{x} \right\rfloor,\left\lfloor \dfrac{K}{y} \right\rfloor$ 个。

观察样例，基本猜出答案为 $\min(\left\lfloor \dfrac{K}{x} \right\rfloor,\left\lfloor \dfrac{K}{y} \right\rfloor)$，也就是说，对于有效长度更小的序列，每一个值都一定都能够找到另一个序列上的值使和 $\geq K$，且这些值可以不重复。

下面给出一个略证，我们把序列 $E$ 的长度设为 $L_E$ ，序列 $C$ 的长度设为 $L_C$：

1. 当 $x<y$：

因为 $x<y$，所以 $L_E \leq L_C$。

则对于 $E_1$ 来说，它要匹配到的 $C_i$ 使得 $C_i+E_1 \geq k$，则必须满足 $i \geq \left\lceil \dfrac{K-E_1}{x} \right\rceil$，为了使答案最优，需要尽量取 $i=\left\lceil \dfrac{K-E_1}{x} \right\rceil$，为了方便表达，我们令 $p=\left\lceil \dfrac{K-E_1}{x} \right\rceil$，此时 $E_1+C_p \geq K$。

继续考虑 $E_2$，我们知道 $E_2-E_1=y$，$C_p-C_{p-1}=x$，则 $E_2+C_{p-1}-(E_1+C_p)=E_2-E_1+C_{p-1}-C_p=y-x>0$，所以 $E_2+C_{p-1}$ 也一定 $\geq K$。

所以对于所有的 $E_j+C_{p-j}(j < p)$，都一定 $\geq K$。那么前 $p$ 个 $E_j$ 就全部可以匹配到相应的 $C_i$。

此时会剩下一些 $E_j$，这些 $E_j$ 都一定比之前的 $E_j$ 大；此时还会剩下一些 $C_i$，这些 $C_i$ 也都比之前的 $C_i$ 大。所以在剩下的所有序列元素中，任意选择 $i,j$ 匹配都会满足要求。

而又因为 $L_E<L_C$，所以剩下的 $E_j$ 都一定可以匹配到 $C_i$，且匹配完还有剩余。

两部分相结合，则得到结论：$\forall\ 1 \leq j \leq L_E$ 都能成功匹配。

2. 当 $x>y$，与上述情况相同。

3. 当 $x=y$：

此时 $L_E=L_C$，则 $E_{L_E}+C_1>E_{L_E}+(K-E_{L_E})=K$，即 $E_{L_E}+C_1>K$，其他情况类似，所以这时也是能全部成功匹配的。

综上，答案就是 $\min(\left\lfloor \dfrac{K}{x} \right\rfloor,\left\lfloor \dfrac{K}{y} \right\rfloor)$。

还有一个要注意的点是 $x=0$ 时，一个序列全部为 $0$，此时如果 $y \nmid K$ 是无解，而 $y \mid K$ 时序列的最后一项匹配另一个序列的任意一项即为唯一满足条件的解。$y=0$ 类似。

所以就可以写程序了，总复杂度 $\mathcal O(T)$。

Code

ll T,x,y,k;
int main(){
	T=read();
	while(T--){
		x=read(),y=read(),k=read();
		if(x==0&&y==0){
			writeln(0);
			continue;
		}
		if(x==0)writeln(k%y==0?1:0);
		else if(y==0)writeln(k%x==0?1:0);
		else writeln(min(k/x,k/y));
	}
	return 0;
}

后记

这道题好像劝退了不少人，但是我觉得没那么难（

最后还是祝洛谷月赛越来越好。