[CCPC2019网络赛] 1008-Fishing Master（思维）

>传送门<

题意：现在需要捕$n$条鱼并且将它们煮熟来吃。每条鱼要煮相应的时间才能吃(可以多煮一会)，锅里每次只能煮一条鱼，捕一条鱼的时间是相同的，但是在捕鱼的时间内不能做其他事(比如换一条鱼煮)，求把所有的鱼都煮熟最少需要多少时间。
思路：这里提供一种比较好理解的想法，来自$yx$学长

你想一下，我们要吃鱼的话鱼肯定是要煮熟的，所以煮鱼的时间必须要花出去，我们这里可以先把煮鱼的时间统计到一起。题目是要求我们尽可能的节省时间，所以我们除了第一条鱼以外，其他的鱼可以在煮的时候钓，这样能最大利用时间。

对于第$i$条鱼，炖它的时候我们可以不浪费时间抓到$t_{i}/k$条鱼，或者浪费$k-t_{i}\%k$的时间抓到$t_{i}/k+1$条鱼.所以如果$\sum_{i=1}^{n}t_{i}/k\geq n-1$，则可以不浪费时间完成任务；如果$\sum_{i=1}^{n}t_{i}/k<n-1$，则差$m$条鱼就选炖$t_{i}\%k$前$m$大的鱼的时候浪费时间多抓一条鱼。

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

int t, n, k, x;

int a[100005];

int main()

{

    scanf("%d", &t);

    while (t--) {

        scanf("%d%d", &n, &k);

        ll cnt = 0, ans = k; //钓第一条鱼的时间

        for (int i = 1; i <= n; i++) {

            scanf("%d", &x); ans += x;

            cnt += x / k; //每条鱼煮的时候能够钓多少条鱼

            a[i] = x%k;

        }

        sort(a + 1, a + n + 1);

        for (int i = n; i >= cnt + 2; i--) //剩下的鱼还需要多煮几分钟才能钓上来

            ans = ans + k - a[i];

        printf("%lld\n", ans);

    }

}

巴特西

[CCPC2019网络赛] 1008-Fishing Master（思维）

最新文章

热门文章