•参考资料
•题意
池塘里有 n 条鱼，捕捉一条鱼需要花费固定的 k 时间；
你有一个锅，每次只能煮一条鱼，其中煮熟第 i 条鱼至少需要 ti 时间；
你在煮鱼的时候可以选择去钓一条鱼，也可也选择不钓；
但是，一旦你决定钓鱼，就必须花费 k 时间调到一条鱼；
任何时刻，你都可以有多条鱼待煮；
问将所有的鱼钓上来并煮熟所有的鱼最少需要多少时间；
•题解
理想的方案是只有在钓第一条鱼的时候锅是空的，其余任意时刻，锅都在做有用功；
锅在做有用功指的是第 i 条鱼在锅中煮的前 ti 时间，多煮的时间称锅在做无用功；
这种情况下，只需要且必须花费 $k+\sum_{i=1}^{n}t_i$ 时间就可以将所有鱼全部钓上来并全部煮好；
那么，实际情况并非如此，要想花费最少的时间，首先得明确在什么情况下可能会导致时间浪费；
假设你当前煮的鱼需要花费 t 时间，钓鱼需要花费 k 时间；
你可以在这 t 时间内钓 $\frac{t}{k}$ 条鱼上来，在钓鱼的时间，锅处于煮鱼状态；
但是剩下的 t%k 时间不足以再钓一条上来；
此时，你就有两个决策可以选择：
决策1：去钓下一条鱼；
决策2：等待 t%k 时间往锅中放入下一条鱼；
当然，选择 决策2 的前题是你得有鱼可煮；
如果你手中有鱼的话，肯定要选择 决策2，因为等待的这 t%k 时间是必须的；
而如果选择 决策1，那么煮当前这条鱼会花费 t+k-t%k 时间，前 t 时间锅在做有用功，是必须的；
但是后 k-t%k 时间，锅就在做无用功，是在浪费时间；
如果你当前手中无鱼，那么你不得不去钓鱼，那么就一定要浪费当前的 k-t%k 时间么？
假设你现在已经煮了 i 条鱼（包括当前煮的这条鱼）；
那么，你完全可以在前 i 条鱼中找个 tj%k（$j \in [1,i]$）大的从而使得浪费的 k-tj%k 时间尽可能的小；
找 tj%k 大的就可以使用优先级队列了；
那么，接下来就要分析一下优先钓哪条鱼了；
当然是优先钓煮的时间较长的鱼了，因为在煮这条鱼的时候，你会尽可能多的钓上来其他的鱼，从尽可能多的选择决策2；
•Code
View Code1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const int maxn=1e5+50; 5 6 int n,k; 7 int t[maxn]; 8 priority_queue<int >q; 9 10 bool cmp(int a,int b) 11 { 12 return a > b; 13 } 14 ll Solve() 15 { 16 while(!q.empty()) 17 q.pop(); 18 19 /** 20 花费k时间钓上来第一条鱼 21 */ 22 ll ans=k; 23 ll cnt=1; 24 sort(t+1,t+n+1,cmp); 25 26 for(int i=1;i <= n;++i) 27 { 28 ans += t[i];///煮第i条鱼 29 cnt += t[i]/k;///再煮的时间可以额外钓t[i]/k条 30 31 if(cnt < i)///如果在煮第i条鱼的时候并没有将第i条鱼钓上来 32 { 33 ans += k-q.top();///选择在t%k最大的那条鱼后钓第i条鱼 34 q.pop(); 35 } 36 q.push(t[i]%k); 37 } 38 return ans; 39 } 40 int main() 41 { 42 int T; 43 scanf("%d",&T); 44 while(T--) 45 { 46 scanf("%d%d",&n,&k); 47 for(int i=1;i <= n;++i) 48 scanf("%d",t+i); 49 50 printf("%lld\n",Solve()); 51 } 52 return 0; 53 }
