题解： UVA11413 Fill the Containers

ycjjj · 2025-02-25 22:13:12 · 题解

题目简述

有 n 瓶牛奶和 m 个容器，第 i 瓶牛奶的重量是 c_{i}，每个容器的重量是相同的。

现在要求将所有牛奶倒入容器中，同一瓶牛奶不能倒入不同的容器中，且前面的牛奶还没倒入容器时，后面的牛奶不能倒入；前面的容器还没装满时，后面的容器不能装牛奶。

求能让牛奶都倒入容器且不溢出容器容量的最小值。

主要思路

由于答案具有单调性，所以可以使用二分答案，主要思路即将答案 \in [l,r]，每次将答案假设为中间值，即 \lfloor \frac{l+r}{2} \rfloor，根据题目中条件反馈压缩范围，最后确定答案。

在本题中，由于就算 n \le m，即牛奶数小于等于容器数，那么容器的容量也至少为 \max_{i=1}^{n}c_{i}，所以 l 设为 \max_{i=1}^{n}c_{i}；

由于就算 m=1，那么只要这个容器的容量为 \sum_{i=1}^{n}c_{i} 就能满足条件，所以将 r 设为 \sum_{i=1}^{n}c_{i}。

AC Code

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;

#define OUT 0
#define MAMBA return
typedef long long ll;
typedef long double db;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
int man();int main(){MAMBA man();}
inline int _abs(int a) { if (a < 0) return -a; return a; }
inline int _pow(int a, int b) { int x = 1, y = a; while(b > 0) {if (b & 1) x *= y; y *= y; b >>= 1; } return x; }
// ----------------------------

// ----------------------------
int n, m, l, r, c[N];
// ----------------------------
bool check(int x) {
    int cnt = 1, sum = 0;  // cnt 表示现在在装第几个容器，sum 表示当前容器装了多少牛奶
    for (int i = 1; i <= n; i++) {
        if (sum + c[i] > x) {   // 当这个容器再装第 i 瓶牛奶会溢出时，就切换下一个容器
            cnt++;
            sum = 0;
        }
        sum += c[i];
        if (cnt > m) return false;  // 减少时间复杂度，在中途判断如果需要使用的容器数大于 m，则直接返回 false
    }
    return true;
}

int _find() {
    int mid;
    while (l < r) {
        mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    return r;
}

int man() {
    while (cin >> n >> m) {
        l = r = 0;
        for (int i = 1; i <= n; i++) {
            cin >> c[i];
            r += c[i];
            l = max(l, c[i]);
        }
        cout << _find() << endl;
    }
    MAMBA OUT;
}