[编程题] 小易的升级之路
小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2,b3...bn. 如果遇到的怪物防御力bi小于等于小易的当前能力值c,那么他就能轻松打败怪物,并 且使得自己的能力值增加bi;如果bi大于c,那他也能打败怪物,但他的能力值只能增加bi 与c的最大公约数.那么问题来了,在一系列的锻炼后,小易的最终能力值为多少?
输入描述:
输出描述:
输入例子:
输出例子:
题目来源：牛客网-网易2016年研发工程师编程题二。
1. 奖学金
小v今年有n门课，每门都有考试，为了拿到奖学金，小v必须让自己的平均成绩至少为avg。每门课由平时成绩和考试成绩组成，满分为r。现在他知道 每门课的平时成绩为ai ,若想让这门课的考试成绩多拿一分的话，小v要花bi 的时
间复习，不复习的话当然就是0分。同时我们显然可以发现复习得再多也不会拿到超过满分的分数。为了拿到奖学金，小v至少要花多少时间复习。 输入描述:
第一行三个整数n,r,avg(n大于等于1小于等于1e5，r大于等于1小于等于1e9,avg大于等于1小于等于1e6)，接下来n行，每行两个整数ai和bi，均小于等于1e6大于等于1
输出描述:
一行输出答案。
输入例子:
5 10 9
0 5
9 1
8 1
0 1
9 100
输出例子:
43
分析：
完成这个题目需要注意两个问题：
（1）求出最少复习时间，需要优先选择每分的复习时间最小的课程，那么需要对元素对按复习时间递增进行排序；
（2）因为课程数很多，每分复习时间很大，所需最小复习时间需要长整型来存储，以防溢出；
（3）如果所需复习时间小于等于0，需要特殊处理。
测试通过源码：
#include
#include
#include
using namespace std;
bool compare(const vector& vec0,const vector& vec1) {
return vec0[1]
}
int main(int argc,char* argv[]){
int courseNum=0,maxScore=0,average=0;
while(cin>>courseNum>>maxScore>>average){
vector >
regularGrade_effort(courseNum,vector(2,0));
int regularGradeSum=0;//平时总分
for(int i=0;i
cin>>regularGrade_effort[i][0]>>regularGrade_effort[i][1];
regularGradeSum+=regularGrade_effort[i][0];
}
sort(regularGrade_effort.begin(),regularGrade_effort.end(),compare);//按每分的复习时间升序排列
long long int minimumTime=0; //因为每分的复习时间很大，需要长整型，否则溢出，不能通过测试
int needScore=courseNum*average-regularGradeSum;
if (needScore
goto end;
for(int i=0;i
for(int j=0;j
minimumTime+=regularGrade_effort[i][1];
if(needScore==0)
goto end;
}
}
end:
cout
}
}
2.路灯
一条长l的笔直的街道上有n个路灯，若这条街的起点为0，终点为l，第i个路灯坐标为ai，每盏灯可以覆盖到的最远距离为d，为了照明需求，所有灯的灯光必须覆盖整条街，但是为了省电，要求这个d最小，请找到这个最小的d。 输入描述:
每组数据第一行两个整数n和l（n大于0小于等于1000，l小于等于1000000000大于0）。第二行有n个整数(均大于等于0小于等于l)，为每盏灯的坐标，多个路灯可以在同一点。
输出描述:
输出答案，保留两位小数。
输入例子:
7 15
15 5 3 7 9 14 0
输出例子:
2.5
分析：
（1）问题的实质是求一个数组序列中的两个连续元素之间的最大差值，还需要考虑首尾的特殊性；
（2）我为了练习set集合容器，所以使用了set来存储路灯位置，当然你也可以使用vector容器。相对于vector容器，其好处是元素不重复，自动排序，劣势就是迭代器不支持算术加减操作，只支持自增++和自减–操作。
测试通过的源码：
#include
#include
#include
using namespace std;
int main(int argc,char* argv[]){
int n=0,l=0;
set lampPos; //默认升序排列
while(cin>>n>>l){
int pos=0;
for(int i=0;i
cin>>pos;
lampPos.insert(pos);
}
int maxDistance=0;
for(set::iterator
it=lampPos.begin();it!=--lampPos.end();++it){
set::iterator nextIt=++it;
--it;
if((*nextIt-*it)>maxDistance)
maxDistance=*nextIt-*it;
}
float d=(float)maxDistance/2;
//考虑第一个路灯到路的开始位置
if(*lampPos.begin()>d)
d=*lampPos.begin();
//考虑最后一个路灯到路的结束
if(l-*(--lampPos.end())>d)
d=l-*(--lampPos.end());
lampPos.clear();
cout
}
[编程题] 小易的升级之路
小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2,b3...bn. 如果遇到的怪物防御力bi小于等于小易的当前能力值c,那么他就能轻松打败怪物,并 且使得自己的能力值增加bi;如果bi大于c,那他也能打败怪物,但他的能力值只能增加bi 与c的最大公约数.那么问题来了,在一系列的锻炼后,小易的最终能力值为多少?
输入描述:
输出描述:
输入例子:
输出例子:
题目来源：牛客网-网易2016年研发工程师编程题二。
1. 奖学金
小v今年有n门课，每门都有考试，为了拿到奖学金，小v必须让自己的平均成绩至少为avg。每门课由平时成绩和考试成绩组成，满分为r。现在他知道 每门课的平时成绩为ai ,若想让这门课的考试成绩多拿一分的话，小v要花bi 的时
间复习，不复习的话当然就是0分。同时我们显然可以发现复习得再多也不会拿到超过满分的分数。为了拿到奖学金，小v至少要花多少时间复习。 输入描述:
第一行三个整数n,r,avg(n大于等于1小于等于1e5，r大于等于1小于等于1e9,avg大于等于1小于等于1e6)，接下来n行，每行两个整数ai和bi，均小于等于1e6大于等于1
输出描述:
一行输出答案。
输入例子:
5 10 9
0 5
9 1
8 1
0 1
9 100
输出例子:
43
分析：
完成这个题目需要注意两个问题：
（1）求出最少复习时间，需要优先选择每分的复习时间最小的课程，那么需要对元素对按复习时间递增进行排序；
（2）因为课程数很多，每分复习时间很大，所需最小复习时间需要长整型来存储，以防溢出；
（3）如果所需复习时间小于等于0，需要特殊处理。
测试通过源码：
#include
#include
#include
using namespace std;
bool compare(const vector& vec0,const vector& vec1) {
return vec0[1]
}
int main(int argc,char* argv[]){
int courseNum=0,maxScore=0,average=0;
while(cin>>courseNum>>maxScore>>average){
vector >
regularGrade_effort(courseNum,vector(2,0));
int regularGradeSum=0;//平时总分
for(int i=0;i
cin>>regularGrade_effort[i][0]>>regularGrade_effort[i][1];
regularGradeSum+=regularGrade_effort[i][0];
}
sort(regularGrade_effort.begin(),regularGrade_effort.end(),compare);//按每分的复习时间升序排列
long long int minimumTime=0; //因为每分的复习时间很大，需要长整型，否则溢出，不能通过测试
int needScore=courseNum*average-regularGradeSum;
if (needScore
goto end;
for(int i=0;i
for(int j=0;j
minimumTime+=regularGrade_effort[i][1];
if(needScore==0)
goto end;
}
}
end:
cout
}
}
2.路灯
一条长l的笔直的街道上有n个路灯，若这条街的起点为0，终点为l，第i个路灯坐标为ai，每盏灯可以覆盖到的最远距离为d，为了照明需求，所有灯的灯光必须覆盖整条街，但是为了省电，要求这个d最小，请找到这个最小的d。 输入描述:
每组数据第一行两个整数n和l（n大于0小于等于1000，l小于等于1000000000大于0）。第二行有n个整数(均大于等于0小于等于l)，为每盏灯的坐标，多个路灯可以在同一点。
输出描述:
输出答案，保留两位小数。
输入例子:
7 15
15 5 3 7 9 14 0
输出例子:
2.5
分析：
（1）问题的实质是求一个数组序列中的两个连续元素之间的最大差值，还需要考虑首尾的特殊性；
（2）我为了练习set集合容器，所以使用了set来存储路灯位置，当然你也可以使用vector容器。相对于vector容器，其好处是元素不重复，自动排序，劣势就是迭代器不支持算术加减操作，只支持自增++和自减–操作。
测试通过的源码：
#include
#include
#include
using namespace std;
int main(int argc,char* argv[]){
int n=0,l=0;
set lampPos; //默认升序排列
while(cin>>n>>l){
int pos=0;
for(int i=0;i
cin>>pos;
lampPos.insert(pos);
}
int maxDistance=0;
for(set::iterator
it=lampPos.begin();it!=--lampPos.end();++it){
set::iterator nextIt=++it;
--it;
if((*nextIt-*it)>maxDistance)
maxDistance=*nextIt-*it;
}
float d=(float)maxDistance/2;
//考虑第一个路灯到路的开始位置
if(*lampPos.begin()>d)
d=*lampPos.begin();
//考虑最后一个路灯到路的结束
if(l-*(--lampPos.end())>d)
d=l-*(--lampPos.end());
lampPos.clear();
cout
}