题目描述：
$N$ 个无限容量的水缸，每个水缸配备一个容量为 $bucket[i]$ 的水桶。有两种操作：
- 升级水桶：选择一个水桶，容量增加 $1$ 。
- 蓄水：全部水桶接满水，倒入各自的水缸。
每个水缸有最低的蓄水量 $vat[i]$ ，返回至少需要多少次操作。
数据范围：
$1\le N \le 100;0\le bucket[i],vat[i]\le 10^4$
题解：
可以直接枚举需要倒水的次数，这样的话就可以确定每个水桶需要扩充的容量。假设倒水次数为 $k$ ，则水桶需要扩容至 $(vat[i] - 1) / k + 1$ ，也就是 $\lceil vat[i] / k\rceil$ 。枚举 $k$ 时， $k\in [1, \max(vat[i])]$
也可以使用优先级队列。因为操作次数与需要最多倒水次数的缸有关。因此每次选择次数最多的缸，对桶扩容，使其倒水次数减一，然后加入优先级队列。每次都这样进行，直到无法获得更优的解。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
int storeWater(vector<int>& bucket, vector<int>& vat) {
int n = bucket.size(), ans = 1e9, maxx = 0;
for(int i = 0; i < n; ++i)
{
if(vat[i] > maxx) maxx = vat[i];
}
if(maxx == 0) return 0;
int tmp = 0;
for(int k = 1; k <= maxx; ++k)
{
tmp = 0;
for(int i = 0; i < n; ++i)
{
int b_size = (vat[i] - 1) / k + 1;
if(b_size > bucket[i])
{
tmp += b_size - bucket[i];
}
}
ans = min(ans, k + tmp);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int storeWater(vector<int> &bucket, vector<int> &vat)
{
priority_queue<pair<int, int>> q;
int n = bucket.size(), cnt = 0;
for (int i = 0; i < n; ++i)
{
if (vat[i] == 0)
continue;
if (bucket[i] == 0 && vat[i] != 0)
{
bucket[i]++;
cnt++;
}
int times = (vat[i] - 1) / bucket[i] + 1;
q.push({times, i});
}
int ans = 1e9;
if (q.empty())
return 0;
while (cnt < ans)
{
auto out = q.top();
q.pop();
ans = min(ans, cnt + out.first);
if (out.first == 1)
break;
int b_size = (vat[out.second] - 1) / (out.first - 1) + 1;
cnt += b_size - bucket[out.second];
bucket[out.second] = b_size;
q.push({out.first - 1, out.second});
}
return ans;
}
};
|