1785: 數字游戲
時間限制: 1 Sec 內存限制: 128 MB

[提交][狀態][討論版]
題目描述
給定一個整數n。

您可以使用這個數字執行以下任意操作(可能是零)次數:

如果n能被2整除，則用n/2代替n;

如果n能被3整除，則用2n/3代替n;

如果n能被5整除，就用4n/5代替n。

例如，可以使用第一個操作將30替換為15，使用第二個操作將30替換為20，或者使用第三個操作將30替換為24。

你的任務是找出從n中得到1所需的最小步數，或者說這是不可能做到的。

您必須回答獨立于q的查詢。

在新行中打印每個查詢的答案。如果無法從n中得到1，則打印-1。否則，打印所需的最小步數。

輸入
輸入的第一行包含一個整數q(1≤q≤1000)——查詢的數量。

接下來的q行包含查詢。對于每個查詢，都有一個整數n(1≤n≤1018)。

輸出
每行中打印每個查詢的答案。如果無法從n中得到1，則打印-1。否則，打印所需的最小步數。

樣例輸入

7 1 10 25 30 14 27 1000000000000000000

樣例輸出

0 4 6 6 -1 6 72

提示
來源
/*
剛開始看到這題，看了一下n的變化幅度，就沒有多想，直接bfs爆搜。
寫好后運行測試樣例居然答案不對，看了好久才發現傳人bfs的參數類型不一致！！
沒有統一用long long。。。。
改好后，樣例過了，我覺得應該沒問題了。交上去編譯錯誤！！！
百思不得其解，djq告訴我定義的全局數組名next會導致的編譯錯誤，這點ta之前跟我們提過，
但是我沒有記住！！人就是不撞南墻不會重視，現在好了，長記性了。改了全局數組名，提交AC。（再記一遍：定義變量名不要用next，最好加一個myXxx）
細細想一想，這題直接一個while貪心一下就可以解決。肯定要優先用2來使n變化：
如果n能被2整除，則用n/2代替n;
如果n能被3整除，則用2n/3代替n;
如果n能被5整除，就用4n/5代替n。
用2使n變化幅度最大，且用3,5變之后一定會變成可以用2來變得。這從分子2n,4n可知啊~
*/
ac_code:
bfs:

#include <bits/stdc++.h> using namespace std; typedef long long LL; struct point {LL x;LL step;point(){step = 0;} }s; int myStep[5]={2,3,5}; LL bfs(LL n) {s.x = n;queue<point> q;map<LL,int>vis;vis[s.x] = 1;q.push(s);while(!q.empty()){point k;k = q.front();q.pop();if(k.x == 1){return k.step;}point temp;for(int i = 0; i < 3; i++){if(k.x % myStep[i] == 0){switch(i){case 0: temp.x = k.x / 2;break;case 1: temp.x = 2 * k.x / 3;break;case 2: temp.x = 4 * k.x / 5;break;}temp.step = k.step + 1;if(!vis[temp.x]){vis[temp.x] = 1;q.push(temp);}}}}return -1; } int main() {int t;cin>>t;while(t--){LL n;cin>>n;cout<<bfs(n)<<endl;}return 0; }

貪心：

#include <bits/stdc++.h>using namespace std; typedef long long LL; int main() {LL q;scanf("%lld",&q);while(q--){LL n;scanf("%lld",&n);LL ans = 0;while(n != 1){int flag = 0;if(n % 2 == 0){n /= 2;ans++;flag = 1;}else if(n % 3 == 0){n = 2*n/3;ans++;flag = 1;}else if(n % 5 == 0){n = 4*n/5;ans++;flag = 1;}if(!flag) break;}if(n != 1)puts("-1");elseprintf("%lld\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的1785: 数字游戏（贪心/bfs--定义全局数组变量遇到编译错误的问题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。