[hdu 4841]圆桌问题 | 约瑟夫问题 STL-vector

原题

问题描述：
经典的约瑟夫问题，有2n个人，其中n个好人n个坏人，使得删去n人后，剩下的全为好人。m为每次数的人数。
n<=32767

题解：
首先考虑n的范围，暴力肯定行不通，所以会想到线段树……
事实证明，线段树的思想完全可以用vector解决，虽然vector.erase()的复杂度是线性的，不是常数的，但是为啥就能过呢……

关于vector.erase()：
C++ reference 中的 complexity 写的是 “Linear on the number of elements erased (destructions) plus the number of elements after the last element deleted (moving).”， 所以它是线性的……

#include<cstdio>
#include<vector>
using namespace std;
int n,m,pos;
vector <int> v;

int main()
{
    while (~scanf("%d%d",&n,&m))
    {
        v.clear();
        for (int i=0;i<2*n;i++) v.push_back(i);
        pos=0;
        for (int i=0;i<n;i++)
        {
            pos=(pos+m-1)%(v.size());
            v.erase(v.begin()+pos);
        }
        for (int i=0,j=0;i<2*n;i++)
        {
            if (i && !(i%50)) putchar('\n');
            if (j<v.size() && i==v[j])
            {
                j++;
                putchar('G');
            }
            else putchar('B');
        }
        putchar('\n');
        putchar('\n');
    }
    return 0;
}

还是不禁感叹STL的强大？？

[hdu 4841]圆桌问题 | 约瑟夫问题 STL-vector

原文：https://www.cnblogs.com/mrha/p/11955082.html