PKU的1012

1012实际上是一条简化版的Joseph问题。Joseph问题是指从1到n的n个人,围成一圈,给定一个m。首先从1号开始报数,说到m的人就死掉,然后下一个人重新报1。比如n等于6,m等于5,那么死亡的编号顺序是5,4,6,2,3。1012是给出一个k,要求n等于2k,找出一个最小的m,使得后k个人先死。

这道题目实际不难,因为k的规模是0<k<14。就算最大的13,求出m的结果才是2504881。因此,就算逐个枚举,也是不会超时的。何况这个枚举很容易优化,m必须是(k+1)的整数倍或者整数倍加1。

但是,非常无奈,怎样提交,总是超时。一直想不明白,搞了一天一夜,终于明白了。原来虽然k是1到13,但是测试输入数据却有成百上千个,不断重复k的可能值。那么当然也有一大部分是k等于13的数据,测试如此多次,超时也就不出奇了。因此,解决的方法就是弄一个数组和循环,保存k从1到13时,m的值是多少,之后再读输入数据。

pku1012

第一次在Linux下发文章,纪念一下。

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s