专栏文章
题解:CF558C Amr and Chemistry
CF558C题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miovj4n1
- 此快照首次捕获于
- 2025/12/03 01:50 3 个月前
- 此快照最后确认于
- 2025/12/03 01:50 3 个月前
CF558C Amr and Chemistry
题目分析
观察题目,每次操作都可以将 折半或乘 2,模拟这个过程仅需 次,所以 BFS 完全可以,不用其他题解推荐的 01-Trie 或 dp。
具体思路
对于每一组样例,易得最终答案(数的值)不会超过 ,所以用 BFS 把每一个数可以得到的所有数记录下来,最后只需遍历一遍,找到最小的次数对应的一个数即可。要注意的是去重,然后 pair 的常数太大,建议用 struct(我因为 pair 套 pairTLE 了好久),时间复杂度 ,AC 完全没问题
代码
CPP#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;
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...