组装玩具
时间限制: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 行。
一个整数，表示小华最多可以组装多少个玩具。
样例输入
复制样例数据
1 111
样例输出
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。
贪心啥，我贪心了半天，先算所有玩具总和，如果看最多能装多少次，然后在遍历一遍看是否最大次数*y[i]<x[i],然后wr了7次，真实。。。然后我火了，那我先算最小次数，然后剩下来的各种还剩的材料一个个去掉不就行了，就是写起来烦一点，然后最终还是写完了，还是蛮开心的。。。
/**/#include <cstdio>#include <cstring>#include <cmath>#include <cctype>#include <iostream>#include <algorithm>#include <map>#include <set>#include <vector>#include <string>#include <stack>#include <queue>typedef long long LL;using namespace std;int n;LL ans, m;int x[100005], y[100005];struct node{int id, num, tim;//num为剩的，tim为还剩下的次数bool operator <(const node &x)const{return tim > x.tim;//将剩下可以组装玩具次数少的放在前面}};priority_queue<node> q;int main(){//freopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);scanf("%d %lld", &n, &m);for (int i = 1; i <= n; i++){scanf("%d", &x[i]);}LL sum = 0;for (int i = 1; i <= n; i++){scanf("%d", &y[i]);sum += y[i];}int minn = 1e9 + 5;//找出不用万能材料够组成多少个玩具for (int i = 1; i <= n; i++){minn = min(minn, x[i] / y[i]);}ans += minn;//记录次数LL need = 0;//已经用完的材料，如果要在组装玩具，那么接下来需要y[i]个for (int i = 1; i <= n; i++){x[i] -= minn * y[i];//更新每种材料还剩下的个数if(!x[i]){need += y[i];}else q.push(node{i, x[i], x[i] / y[i]});}int tim = 0;//标记前一次组装了几个玩具while(q.size()){node t = q.top();q.pop();int w = y[t.id] - t.num % y[t.id];//假设可以装t.num + 1次，那么t这个材料还要几个m -= w + need * (t.tim - tim + 1);if(m < 0){//如果不能装t.num+1个玩具，那么看最多可以装多少个玩具int tt = m + w + need * (t.tim - tim + 1);if(need) ans += tt / need;//防止need=0运行错误break;}ans += t.tim - tim + 1;//更新可以装玩具的次数tim = t.tim + 1;//更新上次可以装玩具的次数need += y[t.id];//第t.id中材料用完了,那么。。。while(q.size()){node v = q.top();if(v.tim == t.tim){//看可以组装次数相同的，想法同上m -= y[v.id] - v.num % y[v.id];if(m < 0){ans--;break;}need += y[v.id];q.pop();}else break;}if(m < 0) break;}if(m >= sum) ans += m / sum;//如果还有剩余，那么更新ansprintf("%lld\n", ans);return 0;}/**/
