全国建筑行业查询平台_桂林网络公司有哪些_外链发布平台_搜索引擎优化简称

题目：

题解：

#define MIN(a, b) ((a) <= (b) ? (a) : (b))
#define MAX_INT_NUMBER 0x7FFFFFFEtypedef struct {int capital;int profit;
} ProNode;int CompareProfit(const ProNode *a, const ProNode *b)
{   /* 从大到小排序 */return  b->profit - a->profit;
}int findMaximizedCapital(int k, int W, int* Profits, int ProfitsSize, int* Capital, int CapitalSize){int i, j;int maxCap;int flag;/* minIndex最小开始扫描的索引，每次循环扫描第1个资本不够但是利润最大的索引，每次有新的项目收入，都立刻重新从最小索引开始扫描（意味着可能会有原来资本不够，但是利润很大的项目可以重新启动了）*/int minIndex; int minFlag;  /* 第一个资本不够，但是利润最大的索引的辅助标志，辅助判断是否要记录minIndex */ProNode node[ProfitsSize];int maxCnt = MIN(k, CapitalSize);if (k == 0 || CapitalSize == 0 || ProfitsSize == 0) {return W;}for (i = 0; i < CapitalSize; i++) {node[i].profit = Profits[i];node[i].capital = Capital[i];}/* 将所有项目按照利润从大到小排序 */qsort(node, ProfitsSize, sizeof(ProNode), CompareProfit);maxCap = W;minIndex = 0;for (j = 1; j <= maxCnt;) {flag = 0;minFlag = 0;/* 每次扫描剩下的项目，将未访问的，资本允许，利润最大的项目启动 */for (i = minIndex; i < CapitalSize; i++) {if (maxCap >= node[i].capital) {maxCap = maxCap + node[i].profit;                node[i].capital =  MAX_INT_NUMBER;flag = 1;j++;/* 注意：这里是不超时的关键点，如果前面已经有利润大的项目被记录了，要立刻停止，重新判断是否可以启动原来利润大的项目，否则，继续找利润大的项目，可以节省很多循环*/if (minFlag == 1) {break;}  } else if (node[i].capital != MAX_INT_NUMBER && minFlag == 0) {/* 因为资本不够未能启动的项目，记录第一个即可， 下次要从此处开始扫描 */minIndex = i;minFlag = 1;}if (j > maxCnt) {break;}}/* 说明已经没有可以启动的项目了 */if (flag == 0) {break;}}return maxCap;
}