AKU NEGARAKU题解
AKU NEGARAKU
https://ac.nowcoder.com/acm/contest/7818/A
题目描述
链接：https://ac.nowcoder.com/acm/contest/7818/A
来源：牛客网
来源：牛客网
1st Academy is an international leadership training academy based in Kuala Lumpur. Every year, the company trains thousands of people to be supplied to companies around the world. To be fair amongst all the trainees, the company will do the selection process using numbering system. The trainees will choose a number from 1 to N, and one number is not limited to only one trainee. The N represents the total number of companies that request trainees from the academy. A number, M, would be picked at random, and the selection starts with a trainee whose number is 1, and then in every M’th people after that, wrapping around to 1 after N, and ignoring trainees already selected. For example, if N = 15 and M = 6, trainees would be selected in the order: 6, 12, 3, 10, 2, 11, 5, 15, 13, 9, 14, 4, 1, 8, 7. All the selected trainees except the last one (which is number 7) will be supplied to companies outside of Malaysia.
However, Leong preferred to stay and work in Malaysia. To him, there is no better place other than Malaysia. He does not mind being located anywhere as long it is Malaysia. As a friend of him, you could help him to choose a number that will save him from being located outside.
Input
However, Leong preferred to stay and work in Malaysia. To him, there is no better place other than Malaysia. He does not mind being located anywhere as long it is Malaysia. As a friend of him, you could help him to choose a number that will save him from being located outside.
Input
输入描述:
Input will consist of a series of lines, each line containing the number of companies (N) with 1≤N≤15001 \leq N \leq 15001≤N≤1500, and a skipping value (M) with 1≤M≤501 \leq M \leq 501≤M≤50. The values will be terminated by a line consisting of double zeros (0 0) as shown in sample input output.
输出描述:
Output will consist of a series of lines, one for each line of the input. Each line will consist of the number M according to the above scheme.
示例1
输入
15 6 550 23 0 0
输出
7 470
题目大意
n个人围成一个环，从1开始循环计数，踢掉计数为m的倍数的那个人，问最后留下来的人的编号
思路
方法很多：
1.数组模拟循环链表
2.递归
3.普通循环
此题解介绍最简单、最易理解的第三种
思路就是通过普通循环的最后添加if(i==n)i=0;将这个循环首尾遍历，再通过统计忽略的人特判跳出循环即可
AC代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
while(~scanf("%d%d",&n,&m)&&(n||m))
{
int vis[1505]={0};
int cnt=0,nu=0;//nu表示已经忽略的人的个数
for(int i=1; i<=n; ++i)
{
if(nu==n-1)
{
for(int j=1; j<=n; ++j)
if(!vis[j])
printf("%d\n",j);
break;
}
if(!vis[i])
{
cnt++;
if(cnt==m)
vis[i]=1,++nu,cnt=0;
}
if(i==n)//相当于循环链表首尾相连
i=0;
}
}
}
投递美团等公司10个岗位