题目描述

难度分:$1900$

输入$n(1 \leq n \leq 100)$和两个长为$n$的数组$a$，$b$$(1 \leq a[i] \leq b[i] \leq 100)$。

有$n$个水桶，第$i$个水桶装了$a[i]$单位的水，水桶容量为$b[i]$。

花费$1$秒，可以从某个水桶中，转移$1$个单位的水，到另一个水桶。

输出两个数：
把水汇集起来，最少需要多少个桶（换句话说需要倒空尽量多的桶），该情况下至少要多少秒完成？

输入样例$1$

4
3 3 4 3
4 7 6 5

输出样例$1$

2 6

输入样例$2$

2
1 1
100 100

输出样例$2$

1 1

输入样例$3$

5
10 30 5 6 24
10 41 7 8 24

输出样例$3$

3 11

算法

逆向思维+动态规划

由于第一要义是减少盛水的桶数量，因此第一问是比较好求的，直接贪心地选择容积大的桶，直到桶的总容积不少于总水量。可以先对二元组$(a[i],b[i])$按照$b[i]$降序排列，贪心地选择前若干个桶即可，假设最少需要$m$个桶。

关键是第二问，如果正着考虑最少有多少水要转移，是很难做的。正难则反，我们考虑最多有多少水不用转移，然后总的水量减去不用转移的水量就是答案。

状态定义

$f[i][j][k]$表示前$i$个桶中选择$j$个桶，且这$j$个桶的总容积恰好为$k$时，不用转移的总水量。

状态转移

此时其实已经转化成一个01背包问题了，对于状态$f[i][j][k]$，有两种可能：把第$i$个桶选进这$j$个桶，或者不选进这$j$个桶。如果不选，那前$i-1$个桶就已经集齐了$j$个总容积为$k$的桶，否则前$i-1$个桶中只选了$j-1$个桶，总容积为$k-b[i]$，状态转移方程为：

$f[i][j][k]=max(f[i-1][j][k],f[i-1][j-1][k-b[i]]+a[i])$

两者选一个较大值进行转移即可。最后，由于状态定义是恰好为$k$体积，因此还需要遍历一下大于等于总水量$sa$的所有体积，最终的答案为$sa-max_{i=sa}^{sb}f[m][i]$，其中$sb$表示能盛放所有水的桶总容积。

复杂度分析

时间复杂度

对二元素数组的排序时间复杂度为$O(nlog_2n)$，贪心计算$m$的时间复杂度为$O(n)$，动态规划先要循环所有桶$i \in [1,n]$，然后再循环选择的桶数$j \in [1,m]$，最后循环体积，而根据题面的数据范围，总体积的量级是$O(n^2)$级别的，因此总的时间复杂度为$O(n^4)$。

空间复杂度

DP数组$f$是主要的空间瓶颈，第一维可以通过内部倒序遍历优化掉，这样额外空间复杂度为$O(n^3)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 10010;
int n, f[N][M];

struct Bucket {
    int water, capacity;
    bool operator<(Bucket &other) {
        return capacity > other.capacity;
    }
} bucket[N];

int main() {
    scanf("%d", &n);
    int sa = 0, sb = 0, maxSave = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &bucket[i].water);
        sa += bucket[i].water;
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &bucket[i].capacity);
    }
    sort(bucket + 1, bucket + n + 1);
    int m = 0;
    for(int i = 1; i <= n; i++) {
        sb += bucket[i].capacity;
        if(sb >= sa) {
            m = i;
            break;
        }
    }
    memset(f, -0x3f, sizeof(f));
    f[0][0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = m; j >= 1; j--) {
            for(int k = sb; k >= bucket[i].capacity; k--) {
                f[j][k] = max(f[j][k], f[j - 1][k - bucket[i].capacity] + bucket[i].water);
            }
        }
    }
    for(int i = sa; i <= sb; i++) {
        maxSave = max(maxSave, f[m][i]);
    }
    printf("%d %d\n", m, sa - maxSave);
    return 0;
}