n 个人去看电影,本来每人要买一张票,但电影院推出了一个活动:一个身高为 xx 的人可以和身高至少为 2x2x 组合,两人一共只需买一张票。现在给出全体 nn 个人的身高,请问总共至少要买多少电影票?
时间: 2023-04-19 14:00:44 浏览: 81
假设身高从小到大排序后为 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)
阅读全文