首页 > 试题广场 >

[NOIP2007]纪念品分组

[编程题][NOIP2007]纪念品分组
  • 热度指数：294 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。
你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

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


输出描述:
包含一个整数，即最少的分组数目。
示例1

输入

100
9
90
20
20
30
50
60
70
80
90

输出

6

备注:
50%的数据满足：1 ≤ n ≤ 15
100%的数据满足：1 ≤ n ≤ 30000, 80 ≤ w ≤ 200
算法知识视频讲解
查看答案及解析
添加回答
Majestic头像 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)
提交观点

问题信息

NOIP复赛 排序 贪心
难度：
1条回答 3504浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号