Fishing Master HDU – 6709

题目链接：https://vjudge.net/problem/HDU-6709

题意：给出n条鱼的抓捕时间k和煮鱼时间a[i]，你要在最短时间把所有鱼都煮了。（注意你只有一口锅）

思路：首先我们必须要花K时间抓一条鱼，然后考虑最佳状态是你在煮第一条鱼的时间就可以把其他鱼都抓了，那么就没有浪费时间。所以我们只要考虑在煮鱼的情况下能抓多少鱼num+=a[i]/k;如果num>=n-1没有时间浪费，否则少几条就要浪费一点时间，只要对a[i]%k从大到小排序，浪费的时间就是（k-a[i]%k)。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+5;
 4 #define ll long long
 5 ll t,n,k,a;
 6 ll ans;
 7 ll b[maxn];
 8 ll cmp(ll a,ll b)
 9 {
10     return a>b;
11 }
12 int main()
13 {
14     scanf("%lld",&t);
15     while(t--)
16     {
17         ll num=0;
18         ans=0;
19         scanf("%lld%lld",&n,&k);
20         for(int i=1;i<=n;i++)
21         {
22             scanf("%lld",&a);
23             num+=a/k;
24             b[i]=a%k;
25             ans+=a;
26         }
27         if(num>=n-1)
28         {
29             printf("%lld\n",ans+k);
30         }
31         else
32         {
33             sort(b+1,b+n+1,cmp);
34             for(int i=1;i<=n-1-num;i++) ans+=(k-b[i]);
35             printf("%lld\n",ans+k);
36         }
37     }
38     return 0;
39 }