Codeforces 558 C. Amr and Chemistry

概述非常有意思的一道题。 给出\(n\)个数\(a_i\)，每个数可以进行任意次乘2或除2（向下取整）的 *** 作，问总共最少进行多少次 *** 作能够让所有数相等。（\(1 \leq n,a_i \leq 10^5\)） 我们可以考虑维护出每一个数对应的所有变换状态，最后对所有数的变换状态求一个交集。枚举交集内的每个元素，一一带回去求最小值。 然而一个数可以除完再乘，也就是说一个数最多可以对应\(\log^2 n

非常有意思的一道题。

给出\(n\)个数\(a_i\)，每个数可以进行任意次乘2或除2（向下取整）的 *** 作，问总共最少进行多少次 *** 作能够让所有数相等。（\(1 \leq n,a_i \leq 10^5\)）

我们可以考虑维护出每一个数对应的所有变换状态，最后对所有数的变换状态求一个交集。枚举交集内的每个元素，一一带回去求最小值。

然而一个数可以除完再乘，也就是说一个数最多可以对应\(\log^2 n\)个状态。（每除一个2可以乘若干个2回来）。这样的话，如果我们再利用set来维护集合的话实现的复杂度就变成了\(O(n \log^3 n)\)，行不通。

考虑把\(set\)换成桶，最后交集中的元素就是被算到\(n\)次的。可是还有一个问题，这\(log^2 n\)个状态可能是会重复的，这样就会被计算多次。如何避免重复是个问题。

我们发现一个数如果最后一位是0那么除2乘2就会产生重复状态了，所以我们只对所有末尾为1的进行先除再乘的处理。

最后如何统计答案呢？我们假设\(cnt_{i,j}\)表示第\(i\)个数达到状态\(j\)需要几步。假设我们最终枚举到交集的元素为\(k\)，那答案就是\(\sum\limits_{i=1}^ncnt_{i,k}\)。这样我们就看出来了，其实不需要\(cnt\)数组，只需要在用桶记录的时候另外开一个类似桶的数组，累积步数就可以了。

于是\(O(n \log^2 n)\)解决了。

/*DennyQi 2019*/#include <cstdio>#include <algorithm>#include <cstring>#include <queue>#include <map>using namespace std;const int N = 100010;const int P = 998244353;const int INF = 0x3f3f3f3f;inline int mul(const int& a,const int& b){ return 1ll*a*b%P; }inline int add(const int& a,const int& b){ return (a+b>=P)?a+b-P:a+b; }inline int sub(const int& a,const int& b){ return (a-b<0)?a-b+P:a-b; }inline int read(){    int x(0),w(1); char c = getchar();    while(c^'-' && (c<'0' || c>'9')) c = getchar();    if(c=='-') w = -1,c = getchar();    while(c>='0' && c<='9') x = (x<<3)+(x<<1)+c-'0',c = getchar();     return x*w;}int n,lim,ans,x,y,a[N],b[N],sum[N];int main(){    n = read();    for(int i = 1; i <= n; ++i){        a[i] = read();        lim = max(lim,a[i]);    }    for(int i = 1; i <= n; ++i){        x = a[i];        int j = 0,k = 0,las = -1;        while(x > 0){            if(las == 0){                ++b[x];                sum[x] += j;                las = (x&1);                x >>= 1;                ++j;                continue;            }            y = x;            k = 0;            while(y <= lim){                ++b[y];                sum[y] += j+k;                              y <<= 1;                ++k;            }            las = (x&1);            x >>= 1;            ++j;        }    }    ans = INF;    for(int i = 0; i <= lim; ++i){        if(b[i] >= n){            ans = min(ans,sum[i]);        }    }    printf("%d\n",ans);    return 0;}

总结

以上是内存溢出为你收集整理的Codeforces 558 C. Amr and Chemistry全部内容，希望文章能够帮你解决Codeforces 558 C. Amr and Chemistry所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。