题解：CF558C Amr and Chemistry

· · 题解

CF558C Amr and Chemistry

题目分析

观察题目，每次操作都可以将 a_i 折半或乘 2，模拟这个过程仅需 \log _2 n 次，所以 BFS 完全可以，不用其他题解推荐的 01-Trie 或 dp。

具体思路

对于每一组样例，易得最终答案（数的值）不会超过 1 \times 10^5，所以用 BFS 把每一个数可以得到的所有数记录下来，最后只需遍历一遍，找到最小的次数对应的一个数即可。要注意的是去重，然后 pair 的常数太大，建议用 struct（我因为 pair 套 pairTLE 了好久），时间复杂度 O(n \log{n})，AC 完全没问题

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n;
int a[N],num[N],sum[N],vis[N];
struct node
{
    int v,f,s;
};
void bfs(int s)
{
    queue<node> q;
    q.push({a[s],-1,0});
    while(!q.empty())
    {
        int u=q.front().v,f=q.front().f,t=q.front().s;
        q.pop();
        if(u==f || u>N || vis[u]==s) continue;
        vis[u]=s;
        num[u]++;
        sum[u]+=t;
        q.push({u*2,u,t+1});
        q.push({u/2,u,t+1});
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        bfs(i);
    }
    int ans=INT_MAX;
    for(int i=1;i<N;i++)
    {
        if(num[i]==n) 
            ans=min(ans,sum[i]); 
    }
    cout<<ans<<"\n";
    return 0;
}