组装玩具

时间限制: 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 1
1
1

样例输出

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;//如果还有剩余，那么更新ans
	printf("%lld\n", ans);

	return 0;
}
/**/