本文共 2555 字，大约阅读时间需要 8 分钟。

组装玩具

时间限制: 1 Sec 内存限制: 128 MB

题目描述

小华打算用 n 种（编号为 1 到 n）材料组装玩具。其中第 i 种材料的数量为 Xi 个。组装一个玩具需要第 i 种材料 Yi 个。小华另外有 m 个万能材料，每个万能材料可以作为 n 种材料中的任意一个材料使用。

请编程计算小华最多可以组装多少个玩具？

输入

输入共3行。 第1行两个整数n和m，分别表示小华有n种材料和m个万能材料。第2行n个正整数，其中第i个整数Xi表示小华第i种材料有Xi个。 第3行n个正整数，其中第i个整数Yi表示小华组装一个玩具需要第i种材料Yi个。

输出

输出共 1 行。 一个整数，表示小华最多可以组装多少个玩具。

样例输入 Copy

1 1 1 1 样例输出 Copy 2 提示 输入中小华只有1个编号为1的材料，另外还有1个万能材料。组装一个玩具需要编号为1的材料1个。所以可以用1个编号为1的材料和1个万能材料分别组装1个玩具，共可以组装2个玩具。 50%的测试点输入数据保证1≤n≤1000, 1≤m≤104，1≤Xi, Yi≤104。 100%的测试点输入数据保证1≤n≤100000, 1≤m≤109，1≤Xi, Yi≤109。

题意就是给你n个材料，让后用这n个材料组装玩具，组装的玩具必须用这n个材料组装(一开始没怎么读懂题，以为每个材料都可以单独组装一个玩具。。)，让后给你 1 ~ n 个材料需要的个数和原有的个数，以及m个万能材料(可以作为 1 ~ n 任意一种材料)，求出最多能组成的玩具数量。

这个题可以用两种方法来做。

二分比较简单，贪心比较麻烦。

(1)贪心法：

先按照 a[i] / b[i] 排个序，也就是说按不需要万能材料就可以组成第i种材料的个数排序，因为最终组成的玩具数量是由最小的材料数量决定的。关键是记录一下x和y，x是前i个材料+1真实需要(也就是算原来剩下的)的个数，y是前i个材料+1最少需要(也就是算原来剩下的)的个数，因为每次+1的话，需要将前i个材料都+1，应该先用y与m比较，且用完y之后要把y变成x，因为前面剩下的已经掉了，依次模拟过程即可。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

(2)二分：

这个就比较简单了，因为组成的玩具数量具有单调性，所以二分组成玩具的数量即可。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

转载地址：https://blog.csdn.net/DaNIelLAk/article/details/105453023 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！