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

题目链接：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 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);
            // 找出两个人的新位置
		// 本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45540.htm
            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;
}        

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索数据结构
， next
， 位置
， 输出
， 公务员
prev
the dole queue、数据结构 queue、queue 结构体、专题片的结构、专题片结构，以便于您获取更多的相关知识。