例题 4-3 救济金发放（The Dole Queue） UVa 133

本文主要是介绍例题 4-3 救济金发放（The Dole Queue） UVa 133，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

为了缩短领救济品的队伍，NNGLRP决定了以下策略：每天所有来申请救济品的人会被放在一个大圆圈，面朝里面。选定一个人为编号 1 号，其他的就从那个人开始逆时针开始编号直到 N。一个官员一开始逆时针数，数 k 个申请者，然后另一个官员第 N 个始顺时针方向数 m 个申请者，这两个人就出圆圈。如果两个官员数的是同一个人，那个人则出圈，如果选了两个不同的人，则先输出第一个第一个官员数出的那个人，然后2个官员再在剩下的人里面继续选直到没人剩下来，注意两个被选中的人是同时走掉的，所以就有可能两个官员选中一个人。

#include<stdio.h>
#include<string.h>
#define maxn 1000
int a[maxn];
int n, k, m;
int go(int p, int d, int t) //巧妙 {while(t--){do{p = (p+d+n)%n;}while(a[p] == 0);}return p;}
int main(){int people;while(scanf("%d%d%d",&n,&k,&m) == 3 && !(n == 0 && k == 0 && m == 0)){for(int i = 0; i < n; i++ ){a[i] = i+1;}int left = n;//剩余 人数 int p1 = n-1, p2 = 0; // p指向起始处的前一个位置 while(left){p1 = go(p1, 1, k);p2 = go(p2, -1, m);printf("%3d", p1+1);//注意 出队人的序号比索引大 1 （数组下标从零开始的）left--;if(p2 != p1){printf("%3d",p2+1);left--;}a[p1] = a[p2] = 0;if(left)printf(",");	}printf("\n");}return 0;}

go函数每走一步都得到下一个位置

解析:至于下一个位置为什么是p = (p+n+d)%n.其实很简单。因为我们是一步步走的，所以只有两种边界情况。假设当前位置是p(0=<p<n),
第一种边界：p + 1 > n - 1，即 p + 1此时应该是到达0位置，但此时p + 1 = n，如果我们取余数，则（p+1)%T = 0,T = n(T表示这个圆圈的周期大小)。
刚好能符合，又因为T = n，所以(P+T+1)%T还是不变的。
第二种边界: p - 1 < 0, 即 p - 1此时的值是-1，对于这种情况可以反过来看，它是向后退后1个单位，可以看成向前走T - 1个单位即p -1 等效于 p + T - 1
，我们要等到此时的位置，再去余，(P+T-1)%T。
对于情况一、二。可以归纳为(P+T+d)%T,当为顺时针是d取1，否则-1.

这篇关于例题 4-3 救济金发放（The Dole Queue） UVa 133的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！