codeforce之Magic Powder

题目:

The term of this problem is the same as the previous one, the only exception — increased restrictions.

Input

The first line contains two positive integers n and k (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109) — the number of ingredients and the number of grams of the magic powder.

The second line contains the sequence a1, a2, ..., an (1 ≤ ai ≤ 109), where the i-th number is equal to the number of grams of the i-th ingredient, needed to bake one cookie.

The third line contains the sequence b1, b2, ..., bn (1 ≤ bi ≤ 109), where the i-th number is equal to the number of grams of the i-th ingredient, which Apollinaria has.

Output

Print the maximum number of cookies, which Apollinaria will be able to bake using the ingredients that she has and the magic powder.

解答：

首先很很明显这是一个对结果进行二分的题目，

注意要用long long int，同时在判断目标答案是否可行的时候用减法不要用加法，否则可能会溢出

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#define ll long long int
using namespace std;

struct vege {
	ll id;
	ll per;
	ll total;
	ll alre;
	vege() {
	}
};

ll cost(vector<vege> &ingr, int tar,ll k) {
	ll res = 0;
	ll size = ingr.size();
	for (int i = 0; i < size; ++i) {
		if (k < 0)
			return false;
		k = k - (tar *ingr[i].per - ingr[i].total <= 0 ? 0 : tar *ingr[i].per - ingr[i].total);
	}
	if (k < 0)
		return false;
	return true;
}
static bool comp(vege A, vege B) {
	return A.alre < B.alre;
}
int main()
{
	ll n, k;
	cin >> n >> k;
	vector<vege> ingr(n);
	ll per;
	for (int i = 0; i < n; ++i) {
		cin >> per;
		ingr[i].id = i;
		ingr[i].per = per;
	}
	for (int i = 0; i < n; ++i) {
		cin >> per;
		ingr[i].total = per;
		ingr[i].alre = per / ingr[i].per;
	}
	//sort(ingr.begin(), ingr.end(), comp);
	int l = 0;
	int r = ~(1 << 31);
	int res = 0;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		bool co = cost(ingr, mid, k);
		if (co) {
			l = mid + 1;
			res = mid;
		}
		else {
			r = mid - 1;
		}
	
	}
	cout << res << endl;
	//system("pause");
}