Warma的硬币

写在前面

本题改编自USACO-The Fewest Coins,仅扩大了部分数据范围

题目描述

除夕之夜,warma唱完鼠来宝之后从国正中心出来,在寒风中瑟瑟发抖,于是乎决定去金拱门奢侈一把。

吃饭全靠赚赏(sang)钱的warma兜里只有硬币,为了快点吃上饭,她想让硬币转手的次数尽可能最少,即付出去的硬币数与找零得到的硬币数之和(S)最小

市面上流通的硬币共有n(1<=N<=10000)种,面值分别为 \(v_1,v_2,...,v_n\)\(1<=V_i<=120\) )。对于面值为 \(v_i\) 的硬币,warma分别有 \(c_i\) 个( \(0<=c_i<=10000\) )。同时,出于囊中羞涩,warma只打算购买总价值为 \(w\) (1<=w<=10000)的食物和(谢拉)小伙伴们分享。

特别要注意的是,金拱门是国际品牌,各种硬币都很充足,可以满足任意的找零方案。收银员小姐姐也很善解人意,听到warma的要求后,决定用最少的硬币为warma找零

作为只会吹灭火器的音乐(le)人,warma找到了经验丰富的你(你也要过饭?),希望你能帮她算出付出去的硬币数与找零得到的硬币数之和(S)最小是多少。

输入格式

第一行:两个用空格分隔的数字:n和w

第二行:N个用空格分隔的数字: \(v_1,v_2,...,v_n\)

第三行:N个用空格分隔的数字: \(c_1,c_2,...,c_n\)

输出格式

输出最小的付出去的硬币数与找零得到的硬币数之和(S),若无解输出-1。

输入输出样例

输入

1
2
3
3 70
5 25 50
5 2 1

输出

1
3

note:支出25+50,找零5

数据规模

对于40%的数据: \(1<=n<=10, 1<=w<=200, 1<=v_i<=80, 0<=c_i<=100\)

对于100%的数据: \(1<=n<=8000, 1<=w<=16000, 1<=v_i<=200, 1<=c_i<=10000\)

题解

传送门->Warma的硬币题解

----- 本文结束 感谢阅读 -----
0%