n 个人去看电影,本来每人要买一张票,但电影院推出了一个活动:一个身高为 xx 的人可以和身高至少为 2x2x 组合,两人一共只需买一张票。现在给出全体 nn 个人的身高,请问总共至少要买多少电影票?
时间: 2023-04-19 19:00:44 浏览: 39
假设身高从小到大排序后为 h1, h2, ..., hn。
对于每个身高 hi,如果能找到一个身高 hj 满足 hj ≥ 2hi,那么 hi 和 hj 可以组合,只需买一张票。
因此,我们可以从小到大遍历每个身高 hi,看是否存在一个身高 hj 满足 hj ≥ 2hi。如果存在,那么就将 hi 和 hj 标记为已组合,继续遍历下一个身高。如果不存在,那么 hi 就需要单独购买一张票。
最后,所有未被标记的身高都需要单独购买一张票。
代码实现如下:
n = int(input())
heights = list(map(int, input().split()))
heights.sort()
used = [False] * n
count = 0
for i in range(n):
if used[i]:
continue
found = False
for j in range(i+1, n):
if not used[j] and heights[j] >= 2 * heights[i]:
used[i] = used[j] = True
count += 1
found = True
break
if not found:
count += 1
print(count)
相关问题
2、约瑟夫(josephus)环问题:编号为1,2,3,…,n的n个人按顺时针方向围坐一圈,每人
每个人都有一个编号,编号为1到n。开始时,编号为1的人开始报数,接着下一个人报数,直到k为止。报数到k的人出列,然后再从出列的人后面的人开始重新从1开始报数,一直循环下去,直到只剩下一个人。
约瑟夫环问题可以用递归的方式解决。当只有一个人时,这个人就是最后剩下的人;当有大于一个人时,将问题规模缩小到n-1个人,位置也向前移动了k位。所以推导出递推公式:
f(n, k) = (f(n-1, k) + k) % n
其中f(n, k)表示n个人中最后剩下的人的编号。
例如,当 n=5, k=2 时,运用递归公式可得最后剩下的人的编号为:
f(5, 2) = (f(4, 2) + 2) % 5 = (f(3, 2) + 2 + 2) % 5 = (2 + 2 + 2) % 5 = 1
所以当有5个人时,按照顺时针方向围坐一圈,每次报数到2的人出列,最后剩下的人的编号为1。
约瑟夫环问题也可以使用循环方式解决。通过建立一个长度为n的数组来表示n个人的状态,每次报数到k的人将其状态置为false,然后一直循环报数,直到只剩下一个人为止。最后剩下的人的编号即为数组中状态为true的索引位置加1。
7.804371e+143个二维码 全球76亿人每人每秒扫一次二维码要多久才能扫完
首先,7.804371e143可以写成78043710000000000000000000000000000000000000000000000000000000000000000000000。
假设全球76亿人每人每秒扫一次二维码,那么全球每秒扫的二维码数量是:
76亿 * 1 = 7600000000
每秒扫的二维码数量是固定的,那么扫完所有的二维码所需的时间可以使用以下公式计算:
时间 = 二维码数量 / 每秒扫的二维码数量
时间 = 78043710000000000000000000000000000000000000000000000000000000000000000000000 / 7600000000
时间 = 1.026421381578947e+31 秒
换算成年,时间大约是3.25e+23年,远远超过了宇宙的寿命。因此,全球76亿人每人每秒扫一次二维码,是不可能在可预见的未来内扫完这么多二维码的。