选举游戏（京东2016实习生真题）

题目描述
									

小东和其他小朋友正在玩一个关于选举的游戏。选举是通过投票的方式进行的，得票最多的人将获胜。

小东是编号为1的候选者，此外还有其他的候选者参加选举。根据初步的调查情况，所有准备投票的小朋友都有一定的投票倾向性，小东如果要获得胜利，

必须争取部分准备为其他候选人投票的小朋友。由于小东的资源较为有限，她希望用最小的代价赢得胜利，请你帮忙计算她最少需要争取的选票数。

题目大意：

小东参加选举，候选人数确定，候选人拟得票数确定。他不算土豪，拉票能力有限，让解题者寻找最小代价当选的方法，即要想当选，最少再拉多少票？

解题思路：

1.若所有候选人目前的得票期望都不如小东，此时不用拉票

2.若候选人中最大的得票期望和小东持平，小东随便拉一票即可

3.若小东的得票期望低于候选人中得票期望的最大值：

   do

   {

      候选人中得票期望最大值-1，小东票数+1

   } while(小东票数 >= 候选人中得票期望最大值)

   if(小东票数 == 候选人中得票期望最大值)

      小东目前票数 - 初始票数 + 1

   else if(小东票数 > 候选人中得票期望最大值)

      小东目前票数 - 初始票数

用Python实现：

while 1:
    a = int(input())
    lst = map(int,raw_input().split())
    xd = lst[0]
    beginxd = xd
    lst = lst[1:]
    if xd>max(lst):
        print 0
    elif xd == max(lst):
        print 1
    else:
        lst = sorted(lst,reverse=True)
        while 1:
            if xd < lst[0]:
                xd += 1
                lst[0] -= 1
                lst = sorted(lst, reverse=True)
            elif xd == lst[0]:
                print xd - beginxd + 1
                break
            else:
                print xd - beginxd
                break

结果：