题目链接

https://codeforces.com/problemset/problem/558/C

解题思路

大佬都说这叫暴力,但是这技巧性也太足了吧……
整体思路:
暴力枚举每个数能到达的数,并记录下到达该数的步数,最后找到每个数都能到达且步数之和最小的数输出。

详细思路:
找最后的答案没必要再暴力统计,我们可以同cnt[i]记录开始的n个数中能到达数值为i的个数;同时用step[i]记录所有开始的n个数到达数值为i的步数之和。

最后输出的答案最大也就是开始n个数中的最大值。(证明我真不会,就是种感觉吧……乱蒙
(这是大佬的解释,但是我没看懂:最大的交点最多是输入的最大值mx,因为如果要去往大于mx的点必须经过mx这个点那么与最小的步骤数矛盾。)

扫描每个起点,先一直右移到mx,再回到这个起点开始左移,左移前检查这个点是奇数还是偶数,如果是偶数,继续左移;如果是奇数,那么左移后再右移到mx,然后继续左移。也就是在左移过程中只要遇到一个节点是奇数,就要叉开一条路,让这个奇数先除2再不断的乘以2,但是原本的左移路线一直不变,只是多了一些路线而已,如果不能理解画一下就明白了。

为什么一遇到奇数,就要先除2,再乘2至mx?
奇数嘛,整除嘛,能理解了吗?哈哈哈哈我好坑,就比如15,先整除2,得到7,再整除2,得到3,你用7不断乘2乘至mx,与你用3不断乘2乘至mx路上经过的数每个都不一样,写一下,7->14->28->56->……,3->6->12->24->48->……。还是证明不会,但是能蒙出来……

数组cnt[]和step[]要开2*10^5,虽然我们推出来终点的极限是输入的最大值mx,mx<10^5,但是由于在算的过程中可能会算到大于mx的数(尽管这对于答案没有贡献),所以数组只开10^5的话,就小了,所以就WA了

画个图来解释一下过程:
图片说明
把整个过程种遇到的数的次数和步数和都统计下来。

AC代码

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+5;
const int INF=0x3f3f3f3f;

int a[N<<1],cnt[N<<1],step[N<<1],mx,n,ans=INF;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        mx=max(a[i],mx);
        cnt[a[i]]++;
    }
    for(int i=1;i<=n;i++) 
    {
        int tmp=a[i];
        int tot=0;
        while(tmp<=mx)
        {
            tmp<<=1;
            ++tot;
            cnt[tmp]++;
            step[tmp]+=tot;
        }    
        tmp=a[i];
        tot=0;
        while(tmp>1)
        {
            if(tmp&1)//奇数,就先整除2,再乘2至mx
            {
                int tt=tmp>>1,cc=tot+1;//注意步数从tot+1开始
                while(tt<=mx)
                {
                    tt<<=1;
                    ++cc;
                    cnt[tt]++;
                    step[tt]+=cc;//累加的要含tot,因为我们得先把开始的数变成tt才能再不断乘2
                }
            }
            tmp>>=1;//无论是不是奇数都要不断整除2
            ++tot;
            cnt[tmp]++;
            step[tmp]+=tot;

        }
    }

    for(int i=1;i<=mx;i++)
    if(cnt[i]==n) ans=min(ans,step[i]);//开始的n个点都能达到,就找到步数最小的
    printf("%d\n",ans);

    return 0;
}

REF

https://blog.csdn.net/AC_0_summer/article/details/47026803