普通队列,提交显示运行错误。
想问一下队列一般多大会爆?我的程序在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;
}