51nod 1693 水群（思维，最短路，spfa）-白红宇的个人博客

51nod 1693 水群（思维，最短路，spfa）

发布日期：2021-11-02 09:48:58 浏览次数：1 分类：技术文章

本文共 1329 字，大约阅读时间需要 4 分钟。

1693 水群

总所周知，水群是一件很浪费时间的事，但是其实在水群这件事中，也可以找到一些有意思的东西。

比如现在，bx2k就在研究怎样水表情的问题。

首先，bx2k在对话框中输入了一个表情，接下来，他可以进行三种操作。

第一种，是全选复制，把所有表情全选然后复制到剪贴板中。

第二种，是粘贴，把剪贴板中的表情粘贴到对话框中。

第三种，是退格，把对话框中的最后一个表情删去。

假设当前对话框中的表情数是num0，剪贴板中的表情数是num1，

那么第一种操作就是num1=num0

第二种操作就是num0+=num1

第三种操作就是num0–

现在bx2k想知道，如果要得到n(1<=n<=10^6)个表情，最少需要几次操作。

请你设计一个程序帮助bx2k水群吧。

输入

一个整数n表示需要得到的表情数

输出

一个整数ans表示最少需要的操作数

输入样例

233

输出样例

简述

这个题出的真的巧妙，说实话，我最开始是没想到是拿最短路写的。

一个数x，操作1是x∗=k代价为k，操作2是x−−代价为1，求把x从1变到n的最小代价。

代码实现

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          #include 
           
            #define inf 0x7fffffffusing namespace std;const int maxn = 1e6 + 10;int n;// 距离int dis[maxn];// 是否在队列int vis[maxn];int p[6] = { 2, 3, 5, 7, 11, 13};void init() { for (int i = 0; i < maxn; i++) { dis[i] = inf; vis[i] = 0; }}void spfa(int u) { init(); dis[u] = 0; vis[u] = 1; queue
            
              q; q.push(u); while (!q.empty()) { u = q.front(); vis[u] = 0; q.pop(); for (int i = 0; i < 6; i++) { if (u * p[i] < n + 4 && dis[u * p[i]] > dis[u] + p[i]) { dis[u * p[i]] = dis[u] + p[i]; if (!vis[u * p[i]]) { vis[u * p[i]] = 1; q.push(u * p[i]); } } } if (dis[u - 1] > dis[u] + 1) { dis[u - 1] = dis[u] + 1; if (!vis[u - 1]) { vis[u - 1] = 1; q.push(u - 1); } } }}int main() { cin >> n; spfa(1); cout << dis[n] << endl; return 0;}

转载地址：https://blog.csdn.net/weixin_43820352/article/details/111301842 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：逆序对模板

下一篇：51nod 1175 区间中第K大的数（主席树）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！