首页 > 试题广场 >

[NOIP2007]纪念品分组

[编程题][NOIP2007]纪念品分组

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

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入描述:

第 1 行包括一个整数 w，为每组纪念品价格之和的上限。
第 2 行为一个整数n，表示购来的纪念品的总件数。
第 3 ~ n+2 行每行包含一个正整数 p_i ( 5 ≤ p_i ≤ w ) ，表示所对应纪念品的价格。

输出描述:

包含一个整数，即最少的分组数目。

示例1

输入

输出

备注:

50%的数据满足：1 ≤ n ≤ 15
100%的数据满足：1 ≤ n ≤ 30000, 80 ≤ w ≤ 200

算法知识视频讲解

Majestic

class solution:
    def distributePrize(self,w,n,price):
        w = int(w)
        n = int(n)
        price = [int(item) for item in price]
        #贪心算法，先进行排序
        sortPrice = sorted(price)
        i,j = 0 ,n-1
        total = 0
        while (i<=j):
            if sortPrice[i]+sortPrice[j] <= w:
                i += 1
                j -= 1
            else:
                j-=1
            total += 1
        print(total)

if __name__ == "__main__":
    w = input()
    n = input()
    price = []
    for i in range(int(n)):
        price.append(input())
    solution().distributePrize(w,n,price)

发表于 2019-08-25 16:35:54 回复(0)