题解：CF1901C Add, Divide and Floor

Jerrycyx · 2024-11-11 14:55:59 · 题解

首先，题目要求使所有的 a_i 相同，而这只与它们的相对大小关系有关。

容易发现其相对大小关系只与每次所选的 x 奇偶性有关，而与 x 的具体大小无关，比如 x=0 和 x=2 不会改变 a 的相对大小关系（后者相对于前者，所有元素都增加了 1，相对大小关系不变）。

所以，令 x 只有 0 和 1 两种选择。每一次操作，所有的 a_i 都变为 \lfloor \frac{a_i}{2} \rfloor 或 \lfloor \frac{a_i+1}{2} \rfloor，使用 \log_2 \max a 级别的操作次数就可以将所有数都变为 0，也就是说，最大操作次数是 \log 级别的。

而要将所有数变为一样，自然可以想到将所有数全部变为最小值 \min a，而每次取 x = \min a 就可以让最小值维持不变，其它数全部变为 \lfloor \frac{a_i + \min a}{2} \rfloor。根据上文，操作次数是 \log 级别的，所以直接暴力改变数值并判断即可，时间复杂度 O(n \log a)。

核心代码：

while(true)
{
    int is_ok=true;
    for(int i=1;i<=n;i++)
        if(a[i]!=a[1]) is_ok=false;
    if(is_ok) break;
    ans++; 
    for(int i=1;i<=n;i++)
        a[i]=(a[i]+mina)>>1;
}

AC 记录 + 完整代码