30分钟实在太紧
基础实在太不扎实
说多了都是泪
题目描述:
N个人抢红包,面额有1,5,10,终极红包是10000,每个人依次抢红包。抢到红包为10的退出,最后留下的人拿10000的红包,问最后是谁拿到10000的红包。
模型建立
本质上就是N个人报数,报到数为3的人退出,然后下一个人接着报一,当报到最后一个人时,就回到第一个人重新报数,但是注意如果最后一个人报的是2,那么第一个人就要接着报3。人数会越来越少,所以最后剩下的人就是拿到最大红包的人。
暴力解法
时间就30分钟,也不知道这种相关算法,直接硬着头皮解,大致思路是把n个人存为一个数组,(元素下标+M)mod 3==0的,让这个元素为零。然后把元素为零的去处掉,形成新的数组,最后剩下一个数就是所求。
关键问题是,前一次最后一个人报的数和整个数组的长度将影响下一次M的取值,其实就是前一次M的取值和数组长度直接影响后一次M的取值,直接暴力枚举有九种可能,详情见后面程序。
程序实现
用python写相关程序:
#!/usr/bin/env python2
# -*- coding: utf-8 -*-
"""
Created on Fri Mar 17 13:23:46 2017
@author: Kakarotto
"""
def union(lst_1):
lst_2=[]
for i in lst_1:
if i!=0:
lst_2.append(i)
return lst_2
def clear_lst(lst_1,m):
for index,i in enumerate(lst_1):
if (index+m)%3==0:
lst_1[index]=0
return lst_1,len(lst_1)
n=input()
lst=range(n+1)[1:]
m=1
for i in range(n):
lst,leng=clear_lst(lst,m)
if m==1:
if leng%3==1:
m=2
elif leng%3==2:
m=0
else:
m=1
elif m==2:
if (leng-2)%3==1:
m=2
elif (leng-2)%3==2:
m=0
else:
m=1
else:
if (leng-1)%3==1:
m=2
elif (leng-1)%3==2:
m=0
else:
m=1
lst=union(lst)
if len(lst)==1:
break
print lst[0]
然而尼玛时间不够啊,if条件我没枚举完,说多了都是泪。
正确解法
微信询问647(某大牛),告诉我是约瑟夫环问题,遂百度之,吐了一口老血。。。。。。。。
其实这个数学模型非常简单,大致思想如下: 首先我们来模拟一下算法操作,假设这个数列为:
[1,2,3,4,5,6,7,8,9,10]
我们首先让第一个人出列,然后将前面的数放在最后得到这样的数列:
[4,5,6,7,8,9,10,1,2]
所以每次操作我们只操作一次,然后将前面的数放在最后去,得到新的数列,然后继续下次操作。
我们假设这个数列长为n,报到第k个数的人出列。我们再假设最后留下的人的下标为f(n,k),注意这个下标是在数列长度为n的情况,当按上述操作一次后,长度就会变为n-1,且由于我们把数列进行了变换,使得这时候最后留下的人的坐标在操作一次后有了改变。改变为多少呢? 显然两种情况:
- f(n-1,k)=f(n,k)-k
- f(n-1,k)=f(n,k)+n-k
所以整理上面的等式,再注意f(n-1,k)下标是不能超过n的,所以我们有递推等式:
f(n,k)=(f(n-1,k)+k)%n
这个递推等式是从f(1,k)开始的,很显然f(1,k)剩下的人在长度为1的数列下标为0,所以根据上面的递推就能很快的算出,最后留下的人是多少了。
n=input()#输入人数
k=input()#输入报数要出去的数字
f=0
for i in range(n+1)[2:]:
f=(f+k)%i
print f+1
继续吐了一口血。。。。。。。
时间完全绰绰有余。。。。。。。。