题解：UVA11413 Fill the Containers

题目传送门

题意

有

n

瓶牛奶，我们要将这

n

瓶牛奶倒入

m

个容器当中，其中：

一个瓶子中的牛奶必须全部倒入容器之中。
先出现的容器先装牛奶。
靠在前面的容器只能被更靠前的容器装牛奶。

现在我们有

m

个用来装牛奶的容器，试求这

m

个容器中容量最大的容器的最小容量。

思路

看到“试求这

m

个容器中容量最大容器的最小容量”，显而易见，这道题就是一道二分答案题。

我们用二分的左边界来解决，将序列分割成

m

个子序列，二分答案的时候把选择的序列跟

m

比较即可。

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n, m, a[1001];

bool check(int x) {
    int temp = 1, sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += a[i];
        if (sum > x) {
            temp++;
            sum = a[i];
        }
    }
    return temp <= m;
}

signed main() {
    while (cin >> n >> m) {
        int maxn = INT_MIN, sum = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            sum += a[i];
            maxn = max(maxn, a[i]);
        }
        int left = maxn, right = sum;
        while (left < right) {
            int middle = (left + right) / 2;
            if (check(middle)) {
                right = middle;
            } else {
                left = middle + 1;
            }
        }
        cout << right << endl;
    }
    return 0;
}

代码说明

输入部分：
- 读取 $n$ 和 $m$ ，表示牛奶瓶数和容器数。
- 读取每瓶牛奶的容量 $a[i]$ ，并计算总容量 $sum$ 和最大容量 $maxn$ 。
二分查找：
- 初始化二分查找的左右边界： $left = maxn$ ， $right = sum$ 。
- 在每次二分中，计算中间值 $middle$ ，并调用 check 函数检查是否可以将牛奶分配到 $m$ 个容器中。
- 根据 check 函数的返回值调整左右边界。
check 函数：
- 模拟将牛奶分配到容器中的过程。
- 如果当前容器的容量超过 $x$ ，则开启一个新的容器。
- 最终判断所需的容器数是否不超过 $m$ 。

复杂度分析

时间复杂度： $O(n \log(\text{sum}))$ ，其中 $\text{sum}$ 是所有牛奶的总容量。
空间复杂度： $O(n)$ ，用于存储每瓶牛奶的容量。

示例

输入：

CPP

5 3
4 2 4 5 1

输出：

CPP

总结

本题通过二分查找和贪心策略，解决了将牛奶分配到容器中的问题。
使用 check 函数验证二分答案的可行性，确保最大容量的最小化。

题解：UVA11413 Fill the Containers

文章操作

题目传送门

题意

思路

代码

代码说明

复杂度分析

示例

输入：

输出：

总结

相关推荐

评论

题解：UVA11413 Fill the Containers