2016年华为机试题

题目

　　描述:

　　题目描述

　　临近开学了，小C才想起来数学老师布置了暑假作业。暑假作业是很多张试卷，每张试卷所需的时间和获取的价值已知，请你帮他安排一下，用他仅剩的一点时间来做最有价值的作业。

　　接口说明

　　原型：

　　int GetMaxValue(int nPapers, int nRemain, int paper[][2], double* pMaxValue)

　　输入参数：

　　int nPapers：试卷的数目(1≤Papers≤20)

　　int nRemain：表示剩余的时间(1≤nRemain≤10000)

　　int paper[][2]：nPapers*2的数组，每一行的两个元素依次为做完这一份试卷所需的时间、做完这份试卷获取的价值。如果剩余时间不够做完一份卷子，可根据剩余时间获得卷子的部分价值。

　　输出参数：

　　double * pMaxValue：获得的最大价值

　　返回值：

　　0:异常，1:成功

　　知识点:

　　工程环境请使用VS2005

　　代码

　　/*---------------------------------------

　　* 日期：2015-06-30

　　* 作者：SJF0115

　　* 题目：Home+Work

　　* 来源：华为上机

　　-----------------------------------------*/

　　#include "OJ.h"

　　#include

　　using namespace std;

　　/*

　　输入: 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 || nRemain < 0 || pMaxValue == NULL){

　　return -1;

　　}//if

　　// 计算性价比

　　double* cost = new double[nPapers+1];

　　for(int i = 0;i < nPapers;++i){

　　cost[i] = (double)paper[i][1] / paper[i][0];

　　}//for

　　//按性价比排序

　　for(int i = 0;i < nPapers-1;++i){

　　for(int j = 0;j < nPapers-i-1;++j){

　　if(cost[j] > cost[j+1]){

　　swap(cost[j],cost[j+1]);

　　swap(paper[j][0],paper[j+1][0]);

　　swap(paper[j][1],paper[j+1][1]);

　　}//if

　　}//for

　　}//for

　　// 计算最大价值

　　int index = 0;

　　int time,value;

　　*pMaxValue = 0;

　　while(nRemain > 0 && index < nPapers){

　　time = paper[index][0];

　　value = paper[index][1];

　　// 剩余时间不足以做一份试卷，取得部分价值

　　if(time > nRemain){

　　*pMaxValue += (double)nRemain / time * value;

　　}//if

　　// 剩余时间可以做一份完整的试卷

　　else{

　　nRemain -= time;

　　*pMaxValue += value;

　　}//else

　　++index;

　　}//while

　　/*for(int i = 0;i < nPapers;++i){

　　printf("时间：%d 价值：%d 性价比：%lf\n",paper[i][0],paper[i][1],cost[i]);

　　}//for*/

　　return 0;

　　}