题解 | #最大养牛利润#

知识点

模拟

思路

可以理解为k次购买，买cost小于当前手上有的钱now，且profits最大的奶牛，不用考虑差价之类的，因为profits就是利润了。然后每一头奶牛只能用一次,可以用一个bool数组记录使用情况。此外，可以先对奶牛依据cost从小到大排序，这样在遍历的时候可以减少一些寻找次数

代码c++

#include <cstring>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param k int整型 
     * @param w int整型 
     * @param profits int整型vector 
     * @param costs int整型vector 
     * @return int整型
     */
    struct cow{
        int p,c,w;
    }a[10006];
static bool cmp(cow a,cow b)
{
    if(a.c!=b.c)return a.c<b.c;
    else return a.w>b.w;
}
    int findMaximizedProfits(int k, int w, vector<int>& profits, vector<int>& costs) {
        // write code here
        cow t;
        int idx=0;
        bool us[10005];
        memset(us,false, sizeof us);
        for(int i=0;i<profits.size();i++)
        {
             t.p=profits[i];
             t.c=costs[i];
             t.w=t.p-t.c;
             a[idx]=t;
             idx++;
        }
        sort(a,a+idx,cmp);    
        int now=w;int ans=0;

        while(k--)
        { 
            int temp=0;
            int cnt=-1;
          for(int i=0;i<idx;i++)
          {    if(a[i].c>now)break;
               if(us[i]==false&&a[i].c<=now&&a[i].p>temp)
               {
                temp=a[i].p;
                cnt=i;
               
               }
          }       
          now+=temp;
          ans+=temp;
         if(cnt!=-1) us[cnt]=true;
         cout<<now<<endl;

        }
return ans;

        
    }
};