刘汝佳算法竞赛入门 ACM/ICPC UVa133 救济金发放-蒲公英云

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

冷不防 2021-12-11 01:51 334阅读 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; 
}