Link

CF1901 C Add, Divide and Floor

Question

给定一个长度为 \(n\) 的序列，每次操作你需要选择一个整数 \(x\) ，并将所有 \(a_i\) 替换为 \(\lfloor \frac{a_i+x}{2} \rfloor\) 。求至少多少次操作后能将所有 \(a_i\) 变相同

若最少次数小于等于 \(n\)，输出操作次数和每次操作所选择的 \(x\)，否则仅输出操作次数

Solution

先思考一个很显然的结论：若 \(a_i \le a_j\)， 无论选取什么样的 \(x\)，\(a_i'=\lfloor \frac{a_i+x}{2} \rfloor\)，\(a_j'=\lfloor \frac{a_j+x}{2} \rfloor\) 有 \(a_i' \le a_j'\)。

所以，对于最小操作次数，我们只需要关注最大值和最小值就好了

由于每次操作只能让最大值和最小值的差值减少一半，所以操作次数就是 \(\log_2 (a_{max}-a_{min})+1\)

得到了操作次数，思考具体怎么操作

操作有一个性质，就是 \(x+2k\) 的作用和 \(x\) 是一样的，其中 \(k\) 是一个整数，也就是说，每次操作和 \(x\) 的奇偶性有关

作为一次操作，假设操作的两个数是 \(a,b (a>b)\) 我们一次操作期望 \(a-b\) 尽量小

那么我们可以分类讨论

• \(a,b\) 同为奇数或偶数，\(x\) 奇偶随意
• \(a\) 偶 \(b\) 奇 \(x\) 为奇数
• \(a\) 奇 \(b\) 偶 \(x\) 为偶数

通过最开始的结论，可知 \(a=a_{max},b=a_{min}\) ，按着模拟即可

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=2e5+5,INF=2e9;
int a[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
void solve(){
    int N=read(),ans=0;
    int Max=-INF,Min=INF;
    for(int i=1;i<=N;i++) a[i]=read(),Max=max(Max,a[i]),Min=min(Min,a[i]);
    int now=Max-Min;
    while(now){
        now>>=1;
        ans++;
    }
    printf("%d\n",ans);
    if(ans<=N){
        for(int i=1;i<=ans;i++){
            int flg=0;
            if((Max&1)==0&&(Min&1)) flg=1;
            else if((Max&1)&&(Min&1)==0) flg=2;
            else flg=1;
            printf("%d ",flg);
            Max=(Max+flg)/2;
            Min=(Min+flg)/2;
        }
        if(ans)printf("\n");
    }
}
int main(){
    int T=read();
    while(T--)solve();
}