题意分析

题意：题目给出n条鱼，以及捕一条鱼所用的时间k，并给出煮每一条鱼的时间，问抓完并煮完所有鱼的最短时间。

思路：

1.捕第一条鱼的时间是不可避免的，煮每条鱼的时间也是不可避免的，这些都要算上。

2.可以优化的是煮鱼的时间，在时间允许的范围内可进行捕其他鱼。当然煮鱼的时间也许不够捕其他鱼，这就需要增加额外的时间。

3.设在煮每条鱼煮的时间内抓的最多的鱼数为cnt，捕鱼的时间为cost，将每次额外增加的时间存储在一个数组中，记为fre[ ]。

4.更多详细信息在代码中给出。

AC代码

/*贪心*/#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;typedef long long LL;const int maxn = int(1e5+10);int T, n, k;int cnt;        //在煮鱼期间最多能钓上来的鱼数int t[maxn], fre[maxn];LL cost;int main(){    // freopen("input.txt", "r", stdin);    // freopen("output.txt", "w", stdout);    scanf("%d", &T);    while(T--)    {        scanf("%d%d", &n, &k);        cost = k;       //捕第一条鱼的时间不可避免        cnt = 0;        memset(t, 0, sizeof(t));        memset(fre, 0, sizeof(fre));        for(int i = 0; i < n; i++)        {            scanf("%lld", &t[i]);            cost += t[i];       //煮鱼的时间不可避免            cnt += t[i] / k;            fre[i] = k - t[i] % k;      //k - 每次煮鱼的时间所剩余的可利用时间 = 多投入的时间        }        if(cnt < n - 1)        {            sort(fre, fre + n);                for(int i = 0; i < n - 1 - cnt; i++)     //贪心思想，从小往大加                cost += fre[i];        }        printf("%lld\n", cost);    }}
        
       
      
     
    

参考博客：