UVa 133：The Dole Queue 数据结构专题

UVa 133：The Dole Queue 数据结构专题2014-10-06 csdn博客 shuangde800题目链接：http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=69

题目类型：数据结构，链表

题意： N份申请书，排成一个圆圈，按逆时针方向编号为1～N。有两个公务员，公务员1站在1，往逆时针方向数到第k份，选中；公务员2站在N，往顺时针方向数到第m份，选中。取走选中的编号的申请书，输出编号。如果编号一样，则只输出一个数。直到所有申请书都拿光。

解体思路：用循环链表模拟，取走的编号从链表中删除。这一题最难的地方在于两个人删除之后，他们的新位置的判断和选择，因为第一个人的新位置可能时第二个人要删除的位置，同理，第二个人的新位置也可能时第一个人要删除的位置。最后，循环结束的判断。这些在代码里会有详细的注释

输入：

10 4 30 0 0

输出：

6, 10,

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
",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）;// 找出两个人的新位置// 本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45540.htmint 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
",pos1,pos2）;break; }if（newPos2==pos2） { printf（"%3d%3d
",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;}