漂流船问题

[编程题]漂流船问题

热度指数：8346 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

公司组织团建活动，到某漂流圣地漂流，现有如下情况：

员工各自体重不一，第 i 个人的体重为 people[i]，每艘漂流船可以承载的最大重量为 limit。

每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。

为节省开支，麻烦帮忙计算出载到每一个人所需的最小船只数(保证每个人都能被船载)。

输入描述:

第一行输入参与漂流的人员对应的体重数组，

第二行输入漂流船承载的最大重量

输出描述:

所需最小船只数

示例1

输入

1 2
3

输出

算法知识视频讲解

Python

我不想当大白菜

，贪心：先排序然后使用left和right指针向中间搜索
- 如果left==right,只剩下一个人，count+1
- 如果和小于等于limit，两个指针向中间移动，count+1
- 否则，right位置的人超重了，单人一个船，count+1

nums = list(map(int,input().split()))
limit = int(input())

count = 0
nums = sorted(nums)
left,right = 0,len(nums)-1
while left <= right:
    if left == right :
        count += 1
        break
    elif nums[left]+nums[right]<=limit:
        left += 1
        right -= 1
    else:
        right -= 1
    count += 1
print(count)

发表于 2020-07-23 19:53:51 回复(0)

Python

牛客835408486号

import math
import bisect

people = sorted(map(int, input().strip().split()))
weight = int(input().strip())

count = 0
while people:
    w = people.pop(0)
    if not people:
        count += 1
        break
    ind = bisect.bisect_right(people, weight - w)
    if ind > 0:
        people.pop(ind - 1)
        count += 1
    elif ind == 0:  # 没找到合适的人，自己乘一辆
        count += 1
print(count)

发表于 2019-09-14 14:12:17 回复(0)

Python

贾志统

def func(weights, limit):
    weights.sort()
    counter = 0
    i = 0
    j = len(weights)-1
    while i <= j:
        counter += 1
        if weights[i]+weights[j] <= limit:
            i += 1
            j -= 1
        else:
            j -= 1
    print(counter)


weights = list(map(int, input().split()))
limit = int(input())
func(weights, limit)

发表于 2019-08-26 22:56:10 回复(0)

Python

欧巴禾

people = list(map(int, input().split()))
limit = int(input())
people = sorted(people)
left = 0; right = len(people)-1
total = 0
while left<=right:
if left==right:
if people[left]<=limit:
total+=1
break
else:
break
number = people[left]+people[right]
if number<=limit:
total+=1
left+=1
right-=1
else:
if people[right]<=limit:
right-=1
total+=1
else:
right-=1
print(total)

发表于 2019-08-16 10:36:41 回复(0)

Python

ElonB

"""
贪心法，重配轻，直到都有船
"""

if __name__ == "__main__":
    people = list(map(int, input().strip().split()))
    limit = int(input().strip())
    people.sort()
    ans = 0
    while people:
        ans += 1
        t = limit - people.pop()
        if not people: break
        if t >= people[0]:
            people.pop(0)
    print(ans)

发表于 2019-07-11 10:01:21 回复(0)