leetcode502. IPO

你的名字 2022-08-28 15:49 182阅读 0赞

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_11_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_11_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_8_color_FFFFFF_t_70_g_se_x_16]  
思路

1.  将利润从大到小排，每次从头开始寻找资本可以覆盖的`captical`，但是这样很容易超时
2.  对寻找进行优化过程，  
    （1）每次寻找的时候从第一个未标记的`captical-profit`项目开始  
    （2）注意有可能找不到合适的投资项目，即使项目还有没标记的，数量资格还没用完，此时需要`break`

#include<stdio.h>
    #include<math.h>
    #include<stdlib.h>
    struct Cu { 
        int profit;
        int capital;
    };
    
    int cmp (const void *a,const void *b) { 
        struct Cu c = *(struct Cu*)a;
        struct Cu d = *(struct Cu*)b;
        return d.profit - c.profit;
    
    }
    int findMaximizedCapital(int k, int w, int* profits, int profitsSize, int* capital, int capitalSize){ 
        int i = 0;
        struct Cu cu[profitsSize]; 
        for (i=0;i<profitsSize;i++){ 
            cu[i].profit = profits[i];
            cu[i].capital = capital[i];
        }
        int max_value = w;
        struct Cu stack[profitsSize*2];
        int start = 0;
        int tempi = 0;
        int flag = 0;
        int minIdex = 0;
        int minflag = 0;
        qsort(cu,profitsSize,sizeof(cu[0]),cmp);
        while (k>0&&count>0)//可以投资的数量和剩余的可投资项目
        { 
            tempi = 0;
            flag = 0;
            minflag = 0;
            for(i=minIdex;i<profitsSize;i++) { 
                if(cu[i].capital<=max_value&&cu[i].profit!=-1&&flag==0) { //因为利润已经从大到小排了，所以第一个符合的就是利润最大的
                    tempi = i;
                    flag = 1;
                }
                if(minflag==0&&cu[i].profit!=-1){ //第一个资本没有标记的profit就是下次搜索的开始
                    minIdex = i;
                    minflag = 1;
                }
                if(flag==1&&minflag==1)//当找到可以投资的项目，以及下一次开始的起始位置，退出此次循环，最差找不到可以投资的项目，需要遍历完整个数组，flag == 0&&minflag==1。或者flag==0&&minflag==0,但是flag==1，minflag必定为1，因为起码是tempi来保底。
                    break;
            }
            if(flag) { 
                max_value = max_value + cu[tempi].profit;
                cu[tempi].profit = -1;
                count--;
                k--;
            }
            else break;//没有一个资本可以覆盖的投资项目
            
    
        }
        return max_value;
    
    }
    
    int main () { 
        int p[3] ={ 1,2,3};
        int c[3] ={ 11,12,13};
        int k =11;
        int w = 11;
        int re = findMaximizedCapital(k,w,p,3,c,3);
        printf("re = %d\n",re);
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_11_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/7b8edd9ae38c466cb35ffd14d807f2d8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_11_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/fb1ebafda53f454890b598be4641706a.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5bmy5ZWl5ZWl5LiN6KGM77yM5ZCD6aWt56ys5LiA5ZCN_size_8_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/124fc05603574af4bffe3e1ceb06c40a.png