2016 Multi-University Training Contest 10 || hdu 5860 Death Sequence（递推+单线约瑟夫问题）

题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=5860

题目大意：给你n个人排成一列编号，每次杀第一个人第i×k+1个人一直杀到没的杀。然后剩下的人重新编号从1～剩余的人数。按照上面的方式杀。问第几次杀的是谁。

分析

一轮过后和原来问题比只是人的编号发生变化，故可以转化为子问题求解，不妨设这n个人的编号是0~n-1，对于第i个人，如果i%k=0，那么这个人一定是第一轮出列的第i/k+1个人；如果i%k!=0，那么这个人下一轮的编号就是i-i/k-1；

#include<stdio.h>

#include<algorithm>

using namespace std ;

#define N 3000000+10

struct no

{

    int d ; ///表示哪一轮被杀

    int num ; ///表示当前轮第几个被杀

    int p ; ///表示本身是几号

}s[N];

bool cmp(no a , no b)

{

    if(a.d==b.d)

    return a.num<b.num;

    return a.d<b.d;

}

int main( )

{

    int T,n,k,q,m;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d %d %d",&n,&k,&q);

        s[].num=;

        for(int i= ; i<n ; i++)

        {

            s[i].p=i+;

            if(i%k==)

            {

                s[i].d=;

                if(i==)

                continue;

                s[i].num=s[i-k].num+;

            }

            else

            {

                s[i].d=s[i-i/k-].d+;

                s[i].num=s[i-i/k-].num;

            }

        }

        sort(s,s+n,cmp);

        while(q--)

        {

            scanf("%d",&m);

            m--;

            printf("%d\n",s[m].p);

        }

    }

}

巴特西

2016 Multi-University Training Contest 10 || hdu 5860 Death Sequence（递推+单线约瑟夫问题）

最新文章

热门文章