救济金发放 (The Dole Queue UVa 133)

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

题目：

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

[objc]  view plain  copy 
 #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.

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