本文主要是介绍UVa 133 - The Dole Queue 数据结构专题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
 | 133 - The Dole Queue | 8487 | 43.29% | 3712 | |
题目类型： 数据结构， 链表
题意： N份申请书，排成一个圆圈， 按逆时针方向编号为1～N。 有两个公务员，公务员1站在1，往逆时针方向数到第k份，选中；公务员2站在N，往顺时针方向数到第m份，选中。 取走选中的编号的申请书，输出编号。如果编号一样，则只输出一个数。 直到所有申请书都拿光。
解体思路： 用循环链表模拟，取走的编号从链表中删除。这一题最难的地方在于两个人删除之后，他们的新位置的判断和选择，因为第一个人的新位置可能时第二个人要删除的位置，同理，第二个人的新位置也可能时第一个人要删除的位置。 最后， 循环结束的判断。 这些在代码里会有详细的注释
输入：
10 4 3 0 0 0
输出：
4 8, 9 5, 3 1, 2 6, 
10, 7
where represents a space.
#include<stdio.h>
#include<string.h>int prev[25];
int next[25];
int N, pos1, pos2,m,n;// 删除节点
void remove(int n){next[prev[n]] = next[n];prev[next[n]] = prev[n];
}void init(){memset(prev,0,sizeof(prev));memset(next,0,sizeof(next));for(int i=1; i<=N;i++){prev[i]=i-1;next[i]=i+1;}prev[1]=N;next[N]=1;pos1=1;pos2=N;
}void solve(){while(1){if(prev[pos2]==pos2 || next[pos1]==pos1 ){printf("%3d\n",pos1);break;}// 第一个人进行移动int stepNum=1;while(stepNum++<m)pos1 = next[pos1];// 第二个人进行移动stepNum=1;while(stepNum++<n)pos2 = prev[pos2];//如果两个人移动到相同的地方if(pos1==pos2){printf("%3d,",pos1);// 找出两个人的新位置int newPos1=next[pos1],newPos2=prev[pos2];// 如果第一个人的新位置是第二个人要删除的位置，那么要再跳过那个位置if(newPos1==pos2) newPos1=next[newPos1];// 如果第二个人的新位置是第一个人要删除的位置，那么也要再跳过那个位置if(newPos2==pos1) newPos2=prev[newPos2];// 把该节点删掉remove(pos1);pos1=newPos1;pos2=newPos2;}else {int newPos1=next[pos1],newPos2=prev[pos2];// 如果第一个人的新位置是第二个人要删除的位置，那么要再跳过那个位置if(newPos1==pos2 ) newPos1=next[newPos1]; // 如果第二个人的新位置是第一个人要删除的位置，那么也要再跳过那个位置if(newPos2==pos1) newPos2=prev[newPos2];// 特别情况：当最后只剩下两个结点，且两个人都选中不同的编号时，则两个都要删掉// 这时候，其中一个人的新位置一定还是它自己原来要删除的位置// 因为另一个要被另一个人删除if(newPos1==pos1) { printf("%3d%3d\n",pos1,pos2);break; }if(newPos2==pos2) { printf("%3d%3d\n",pos1,pos2);break; }printf("%3d%3d,",pos1,pos2);remove(pos1);remove(pos2);pos1=newPos1;pos2=newPos2;}}
}
int main()
{freopen("input.txt","r",stdin);while(scanf("%d %d %d",&N,&m,&n)){if(N==0 && m==0 && n==0) return 0;init();solve(); }return 0;
} —— 生命的意义，在于赋予它意义。
原创 http://blog.csdn.net/shuangde800 ， By D_Double
这篇关于UVa 133 - The Dole Queue 数据结构专题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
