【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;
}