注册 登录
编程论坛 C++教室

普通队列,提交显示运行错误。

青蝶 发布于 2018-08-27 23:15, 1163 次点击
想问一下队列一般多大会爆?我的程序在oj上提交显示运行错误,不知道哪儿有问题。

题目描述:
输入整数a和b(1<=a,b<=1000000),每次可以对一个数进行两种操作:
1.除以2(限偶数)。
2.减去1。
求将a到b的所有数(包括a和b)都变成1最少需要多少次操作?

我的代码:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<algorithm>
using namespace std;

int visited[1000010];
long long int a,b;

struct node{
    int n;
    int step;
}t1,t2,t3;
queue<struct node> q;

int main(void){
   int start,number,k;
   long long int sum;
   while(scanf("%d %d",&a,&b)!=EOF){
       while(!q.empty()) q.pop();
       memset(visited,0,sizeof(visited));
       number=b-a+1;
       k=0;
       sum=0;
       start=1;
       while(start<=a){
        start=2*start;
        k++;
    }
    start/=2;
    k--;
    t1.n=start;
    t1.step=k;
    k=0;
    q.push(t1);
    visited[t1.n]=1;
    if(t1.n>=a && t1.n<=b){
        k++;
        sum+=t1.step;
    }
       while(!q.empty()){
           t1=q.front();
           q.pop();
           t2.n=t1.n+1;
           t2.step=t1.step+1;
           t3.n=2*t1.n;
           t3.step=t1.step+1;
           if(visited[t2.n]==0 && t2.n<=b){
               q.push(t2);
               visited[t2.n]=1;
               if(t2.n>=a){
                 k++;
                 sum+=t2.step;
                 if(k==number) break;
               }
           }
           if(visited[t3.n]==0 && t3.n<=b){
               q.push(t3);
               visited[t3.n]=1;
               if(t3.n>=a){
                 k++;
                 sum+=t3.step;
                 if(k==number) break;
               }
           }
       }
       printf("%lld\n",sum);
   }
   return 0;
}
           
1 回复
#2
rjsp2018-08-28 08:16
为什么不肯贴OJ的原始链接?
1