【2024.10.2练习】奶牛晒衣服

题目描述

题目分析

采用贪心的思路固然正确：每次用烘干机晒最湿的衣服。但是这样一步步模拟，每秒钟都要处理n件衣服的湿度，显然超时。不妨采用二分搜索，遍历所有可行解，求出其中的最小解。

我的代码

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
typedef long long ll;
ll c[500002];
ll c_0[500002];
ll n = 0;
ll a = 0;
ll b = 0;
void arrcopy(ll x[], ll y[]) {
	for (int i = 0; i < n; i++)
	{
		x[i] = y[i];
	}
}
//判断t时间内能否晒干所有衣服
bool Available(ll t) {
	arrcopy(c, c_0);
	for (int i = 0; i < n; i++)
	{
		c[i] -= a * t;
	}
	ll r = t;//剩余时间
	for (int i = 0; i < n; i++)
	{
		if (c[i] > 0 && c[i] % b == 0) {
			r -= c[i] / b;
		}
		else if (c[i] > 0 && c[i] % b != 0) {
			r -= c[i] / b + 1;
		}
	}
	arrcopy(c, c_0);
	if (r < 0) return false;
	else return true;
}
int main() {
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++)
	{
		cin >> c_0[i];
	}
	//Binary Search
	ll lb = -1;
	ll rb = 500002;
	while (rb - lb > 1) {
		ll mid = (lb + rb) / 2;
		if (Available(mid)) rb = mid;
		else lb = mid;
	}
	cout << rb;
	return 0;
}