HDU 6709 - Fishing Master

发表于 更新于 分类于 阅读次数：

题目链接：HDU 6709

考虑什么情况下花费的时间最少。我们要花的必要的时间是\(k + \sum t_i\)，如果所有的捕鱼工作全部能在煮鱼的时候完成。如下图所示：

这种情况花费的时间肯定是最小的，为\(k + \sum t_i\)，但是前提是\(1 + \sum \lfloor \frac{t_i}{k}  \rfloor\geq n\)。但是如果\(t_i\)很小，那么我们可能会牺牲\(k - (t_i \bmod k)\)的时间用来抓鱼，例如这种情况：

于是在 \(1 + \sum \lfloor \frac{t_i}{k}  \rfloor < n\) 的情况下我们可以牺牲前 \(n - (1 + \sum \lfloor \frac{t_i}{k}  \rfloor )\) 个最小的 \(k - (t_i \bmod k)\) 来捉鱼，这样保证牺牲的时间是最小的。

其实我们可以观察到每一次开始煮鱼的时候也是捕新鱼的开始，我们其实只要对每一个这样的单位区间，这样的区间有三种情况，一种是出现捕鱼的时候不能煮鱼（即不等），一种是煮鱼的时候不能捕鱼（即等），一种是 \(t_i \bmod k = 0\)。如果我们把煮鱼的时间看成是必要的，那么我们就要减少因为捕鱼浪费的煮鱼时间；如果我们把捕鱼的时间看作是必要的，那么我们就要减少因为煮鱼浪费的捕鱼的时间，这里也用到了定一个求另一个的思想。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 100000 + 5;
int T, n, k, t[MAX_N], r[MAX_N];
int main() {
    scanf("%d", &T);
    for (int cs = 1; cs <= T; ++cs) {
        scanf("%d%d", &n, &k);
        LL sum = 0;
        for (int i = 1; i <= n; ++i) scanf("%d", t + i), sum += t[i];
        LL cnt = 1;
        for (int i = 1; i <= n; ++i) cnt += t[i] / k;
        if (cnt >= n) printf("%lld\n", k + sum);
        else {
            LL rem = n - cnt;
            for (int i = 1; i <= n; ++i) r[i] = (k - t[i] % k);
            sort(r + 1, r + n + 1);
            for (int i = 1; i <= rem; ++i) sum += r[i];
            printf("%lld\n", k + sum);
        }
    }
    return 0;
}