免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[组合] 编程算法 灌水

灌水(water.pas/c/cpp)
炎热的夏季,新疆吐鲁番地区又赢了一年中最难熬的旱季。作为一个经验充分的农夫,约翰在旱季来临之前购买了大量不同体积的水桶,用于存储灌溉农田的用水。约翰有一个葡萄园,他每天必须给所有葡萄浇灌C升的水,以防止它们因为缺水而枯萎。
已知约翰有体积为Vi的水桶mi个,并且每个水桶都灌满了水。有个不幸的消息时,一个水桶一旦开封后,里面的水必须一次性用完,就算当天不需要如此大量的水,桶里的水也会因为炎热的天气而被蒸发干净。这些水桶的体积的最大公约数为水桶的最小体积。
求问约翰存储的水可以使用多少天。

[输入格式]
第一行,两个正整数N(1<=N<=20)和C(1<=C<=100,000,000)。
第2~N+1行,每行两个整数,表示水桶的体积V(1<=V<=100,000,000)和水桶的数量M(1<=M<=1,000,000)。

[输出格式]
一个整数,代表可以灌溉的天数。

[样例输入]
3 6
10 1
1 100
5 120
[样例输出]
111
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

达到体积c的桶不用管它,一桶一天,
以下对不到c的桶,按体积排序,两两之和正好是c的两桶,搭配起来也是可用一天,不会不够或浪费,然后怎么搭配?

TOP

举个栗子:
假定每天消耗c=10个单位的水
水桶依次有8个单位4桶,3个单位4桶,
那么应该这样可以有4天,8+3,8+3,8+3,8+3,
而不是8+8,8+8,3+3+3+3这样才3天。

TOP

本帖最后由 realnumber 于 2019-8-26 07:15 编辑

继续特殊到一般,探索
每天水量c=9
已有的水桶容量是8,8,8,8,3,3,3,3
那么应该是8+3一共4天,而不是3+3+3,8+3,8+8,三天

每天水量c=9
已有的水桶容量是8,8,8,8,3,3,3,3,2,2,2,2,1
可以是4个8+2,3+3+3,5天多一个容量1,3的桶
也可以3个8+2,8+3,3+3+3也是5天,多一个容量1,2的桶
终止优化一个条件是:当天数达到(总容量/c)时,应该不用优化了
感觉是先搭配完容量大的,....

TOP

返回列表 回复 发帖