题目链接
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;
}
京公网安备 11010502036488号