蓝桥杯2017年第八届真题-分巧克力 （C++代码）

        二分        

参考代码:

#include<bits/stdc++.h>
constexpr auto Inf = 0x3F3F3F3F;
#define Loc freopen("baka.in", "r", stdin)
typedef long long LL;
using namespace std;

const int SIZE = 1E5 + 7;
int Tot, N;
pair<int, int> Arr[SIZE];

bool F(int Mid) {
	int Tmp = 0;
	for (int pos = 1; pos <= Tot; pos++)
		Tmp += (Arr[pos].first / Mid) * (Arr[pos].second / Mid);
	return Tmp >= N;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> Tot >> N;
	for (int pos = 1; pos <= Tot; pos++)
		cin >> Arr[pos].first >> Arr[pos].second;
	int L = 1, R = SIZE, Mid;
	while (L <= R) {
		Mid = (L + R) >> 1;
		F(Mid) ? L = Mid + 1 : R = Mid - 1;
	}
	cout << min(L, R) << endl;
}