CF792B题解

· · 题解

题意

乍一看，不就是约瑟夫环吗？

实际上是这样的

一群编号为 1 \sim N 的人按顺时针围成一个圈。开始位置为 1， 然后给出 K 个数字 a_1 \sim a_i，分成 K 次执行，执行第 i 次时，从开始位置顺时针数 a_i 个数，输出且删除数到的最后一个数，然后开始位置变为被删除的数的下一个数。

普通版本

用一个数组标记数是否已经被删除，若被删除，扫的时候直接跳过。

要注意的是：因为测试数据给出的数是比较大的，所以要先进行求余，如果不这样做，就会超时

自己用的是数组实现，其实这样并不好，处理的时候很麻烦，看下面代码就知道了。......强烈建议用 STL。

代码


#include<iostream>
#include<string>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
#define MAXN 105
bool del[MAXN];
int main()
{
    int n,m;
    int a;
    int p;
    while(cin>>n>>m)
    {
        p=2;//起点是1,所以从2开始数
        int nn=n;
        memset(del,false,sizeof(del));
        while(m--)
        {
            cin>>a;
            if(a%nn)a%=nn;//余数不为0时,求余 
            else if(a>nn)//余数为0且a>nn时,直接等于nn;
            {
                a=nn;
            }
            nn--;
            while(1)
            {
                if(!del[p])
                {
                    a--;
                    if(a==0)
                    {
                        del[p]=true;
                        break;
                    }
                }
                p++;
                if(p>n)p=1;
            }
            if(m!=0)cout<<p<<" ";
            else cout<<p;
            while(del[p])//找起点
            {
                p++;
                if(p>n)p=1;
            }
            //找起点的下一个数，因为是从起点的下一个数开始数的
                        p++;
            if(p>n)p=1;
            while(del[p])
            {
                p++;
                if(p>n)p=1;
            } 
        }
        cout<<endl;
    }
}

STL 版本

前置芝士：deque

deque 是 STL 的一个容器，全名为双端队列容器，具体定义方式和 vector 相似。

有两个重要函数，push_back()，pop_front()，前者可以向队尾插入元素，后者可以弹出（删除）队头元素。

我们可以通过向队尾插入队头元素后弹出（删除）队头元素，从而实现换一个人，即将这个‘圈’转一格。

用 deque 代码实现就是：

a.push_back(a.front());
a.pop_front();

这个弄好之后，其他就都好办了。直接看有没有出列，一个一个人旋转。

代码

#include<iostream>
#include<deque>
using namespace std;
deque<int> a;
int n,k;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    { 
        a.push_back(i);
    }//输入 
    for(int i=0;i<k;i++)
    {       
        int s;
        cin>>s;
        s%=a.size();//注意要取模 
        while(s--)//一个一个旋转 
        {
            a.push_back(a.front());//插入队首项 
            a.pop_front(); //弹出 
        }
        int val=a.front();
        a.pop_front();//out直接弹出
        cout<<val<<" ";//输出 
    }
    return 0;
}