题解 P7441 【Erinnerung】

Unordered_OIer · 2021-03-20 18:50:48 · 题解

P7441 题解

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

Description

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

需要选择 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;
}

后记

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

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