刘汝佳算法竞赛入门 ACM/ICPC UVa133 救济金发放

冷不防 2021-12-11 01:51 185阅读 0赞

## 题目 ##

n(n<20)个人站成一圈，逆时针编号为1～n。有两个官员，A从1开始逆时针数，B从n开始顺时针数。在每一轮中，官员A数k个就停下来，官员B数m个就停下来（注意有可能两个官员停在同一个人上）。接下来被官员选中的人（1个或者2个）离开队伍。  
输入n，k，m输出每轮里被选中的人的编号（如果有两个人，先输出被A选中的）。例如，n=10，k=4，m=3，输出为4 8, 9 5, 3 1, 2 6,10, 7。注意：输出的每个数应当恰好占3列。

思路：  
输入n,k,m之后，用一个数组进行编号，一个元素代表一个人。当队伍里还有人，A走动，B走动，选人，此人离开队伍（离开队伍该元素值变0），用0表示离开队伍的人，数数时跳过即可，A、B继续走动，直到队伍剩下的人为0

函数：  
一个子函数为A、B走动所选中的人，A逆时针走，k步，其下标+1…B顺时针走，走m步，其下标-1，将其一般化，就是在go函数传入参数:当前位置，顺时针/逆时针走（决定了下标的加减），走多少步，返回值为所选中的人的下标。

细节：  
循环条件：Left！=0  
特殊条件：A、B选到同一个人（所以要判断两个所返回的下标是否相等）  
结束条件：队伍内无人，即left==0

讲一下核心代码：若你想将一个数p归到 0- n 的范围（n！= 0 ，1）

只需 p%n

在该题中想控制在1~n之间，所以是（…）%n+1;  
至于括号里的为什么那样写，得自己找规律思考了，我来讲一下我的理解。  
逆时针下标是+1，所以d是1；顺时针下标-1，所以d是-1；A的开始下标是n;A第一步的下标应该为1，所以可用推算出（…里的值应该为n）

#include<bits/stdc++.h>//核心代码：p=(p+d+n-1)%n+1;
    using namespace std;
    int n,k,m,a[30];
    int go(int w,int d,int t)
    {
    	while(t--)//走t步
    	{
    		do{
    			w=(w+d+n-1)%n+1;
    		}
    		while(a[w]==0); //遇到元素=‘0’,即这个人已经离开队伍，继续寻找下一个人，直到出现仍在队伍的人
    	} 
    	return w;
    }
    int main()
    {
    
    	while(cin>>n>>k>>m&&n)
    	{
    		int left=n,p1=n,p2=1;//p1为A的位置 ，为什么是在n 因为走一步的话 就刚好在1后面。
    		for(int i=1;i<=n;i++)
    			a[i]=i;
    		while(left)
    		{
    			p1=go(p1,1,k);//A走动
    			p2=go(p2,-1,m);//B走动
    			printf("%3d",p1);
    			left--;
    			if(p2!=p1)
    			{
    				printf("%3d",p2);
    				left--;
    			 } 
    			a[p1]=a[p2]=0;
    			if(left)
    			{
    				cout<<",";
    			}
    		}
    		cout<<endl;
    	}
    	return 0; 
    }