Home+Work

#include "OJ.h"
 
  
/*


输入: nPapers表示试卷的数目(1≤Papers≤20)，nRemain表示剩余的时间(1≤nRemain≤10000)，paper[][2]是一个Papers*2的数组，


每一行的两个元素依次为做完这一份试卷所需的时间、做完这份试卷的价值


输出: *pMaxValue为获得的最大价值
返回:
0:异常
1:计算成功返回




*/
int GetMaxValue(int nPapers, int nRemain, int paper[][2], double* pMaxValue)
{
   if (nPapers<0 || nPapers>20 || nRemain<0 || nRemain>10000)  
        return 0;   
    *pMaxValue=0;  
    int i,index,timesum=0,timesumMax=0;  
    double temp[20]={0};  
    for (i=0;i     {  
        temp[i]=(double)paper[i][1]/(double)paper[i][0];  
        timesumMax+=paper[i][0];  
    }  
    do  
    {  
        double f=0;  
        for (i=0;i         {  
            if (f             {  
                f=temp[i];  
                index=i;  
            }  
        }  
        temp[index]=0;  
        timesum+=paper[index][0];  
        if (timesum         {  
            *pMaxValue+=paper[index][1];  
        }  
        else  
        {  
            double t=(double)paper[index][1]*(nRemain-timesum+paper[index][0])/(double)paper[index][0];  
            *pMaxValue+=t;  
        }  
    } while (timesum     return 1;
}