本文共 2057 字，大约阅读时间需要 6 分钟。

题目大意：

你需要把一些鱼钓出来并烤熟，鱼钓出来的时间是一定的，而每条鱼煮熟的时间却不一样(但是你知道哪一条鱼要煮多长时间，并且可以选择钓哪一条鱼)，在钓鱼的时候什么都不能干，其余时间可以选择把钓出来的鱼放进锅里，或者把已经熟的鱼从锅里拿出来(可以煮过头 虽然可能已经煮没了)，求最小花费的时间。

思路：

当然是选择在煮鱼的时候尽可能钓上来更多的鱼，那么则分为两种情况：

1. 如果都能在煮鱼的时候把鱼都给钓出来，那就直接输出“钓一条鱼的时间+煮所有鱼的时间“。 2. 如果不能，那就需要利用额外的时间。 在同时钓鱼、煮鱼的时候，会遇到两种情况：1.钓出来一条鱼，然后继续钓下一条。2.等鱼煮熟后，放入一条生鱼再继续钓鱼。 比赛的时候就在苦思冥想到底改如何抉择，到最后也没想出来，直接白给。 其实，假设钓鱼时间是k，正在煮的这条鱼还有a[i]就会熟,那么多余的最短时间就是abs(k-a[i]) 上图为两种不同情况，绿色为钓鱼时间，黑色为煮鱼时间，三角形为除去煮鱼时间的额外的时间 不难发现，不管怎样抉择，额外时间总是 >= abs(k-a[i])，可以自己再试着画几个，就会发现这个规律。 别问我怎么证明，我也不太会。

具体过程：

1..判断是否可以在煮鱼时间内把鱼钓出来 ，可以则直接输出结果，不行则进行进一步计算。

2. 对于每一次煮鱼，我们要在煮鱼时钓尽量多的鱼，那么有可能在钓下一次鱼的时候，时间不够用了，那么我们就统计一下剩余的时间，及直接对k取模。 3. 那么我们就要选择在哪条鱼煮的时候的剩余时间中去钓鱼，不难想到，要使abs(k-a[i)尽量小，那么就要让a[i]尽量大， 所以我们只需要进行一次排序就好了，之后就进行计算了。

代码：

//就尽量写的简单明了了，有很多步骤可以优化，看懂了之后可以试试#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int maxn=1e5+5;int T,n,t[maxn],k,r[maxn],g;long long sum;inline int Read()//快读，OI留下来的习惯{
       int cal=0,f=1;    char ch=getchar();    while(ch>'9'||ch<'0'){
           if(ch=='-') f=-f;        ch=getchar();    }    while(ch>='0'&&ch<='9'){
           cal=cal*10+ch-'0';        ch=getchar();    }    return f*cal;}bool cmp(int x,int y){
       return x > y;}inline void Start(){
       memset(t,0,sizeof(t));    memset(r,0,sizeof(r));    g=sum=0;}int main(){
       T=Read();    while(T--){
           n=Read();k=Read();        Start();        for(int i=1;i<=n;++i){
   //STEP1+2            t[i]=Read();            r[i]=t[i]%k;//计算剩余时间            g+=t[i]/k;//计算可以在煮鱼的时候钓上来的鱼的数量            sum+=t[i];//计算煮鱼所消耗的时间        }        if(g>=n-1){
               printf("%lld\n",sum+k);            continue;        }        sort(r+1,r+1+n,cmp);        int nd=n-1-g;//还剩下多少鱼没被钓出来        for(int i=1;i<=nd;++i)            sum+=(k-r[i]);        printf("%lld\n",sum+k);    }    return 0;}
      
     
    
   

经验与教训：

1. 考试的时候觉得这是道贪心题，就一直认为贪心的重点在于钓鱼的时候是继续钓，还是等待🐟煮好了再去钓，没有意识到时间可以计算出来，不需要知道具体细节。

2. 其实是重点放错位置了，只是觉得这是贪心，就一直在想怎么贪心，而忘记从头开始考虑这道题怎么解，只是一味地为了贪心而想贪心。

如果觉得有用就给个赞吧！

最后送大家一个可爱的唧唧娘吧！

每日中二： 就这么大步向前地走向明天吧！！！！

转载地址：http://iuuci.baihongyu.com/